How to find all the permutations of a variable amount of 0's and 1's recursively (without using itertools or random)?

user_15236155 0
Viewed 73

I'm trying to produce all permutations of a certain number of numbers (for example, 0s and 1s) for a variable number of positions. I will call the number of numbers ord (e.g. ord=2 for only 0s and 1s; ord=3 for 0s, 1s, and 2s) and the number of positions Num. Hence the number of permutations is ord**Num.

Note: I don't want to use itertools or any other types of built-in functions. I'm asking this out of curiosity, not just trying to find a solution.

For ord=2 and Num=3, the output, in any order, should be:

[[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]

This can be accomplished by:

ord = 2 
mylist = []

for a in range(ord):
    for b in range(ord):
        for c in range(ord):
            mylist.append([a,b,c])

For ord = 2 and Num = 4, the output should be:

[[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,0,1,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],[1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1],[1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1]]

But then I would have to add another nested for loop:

ord = 2 
mylist = []

for a in range(ord):
    for b in range(ord):
        for c in range(ord):
            for d in range(ord):
                mylist.append([a,b,c,d])

An obvious solution is to add 0s and 1s randomly to a list of length Num and then to accept that list if it hasn't already been added to mylist, but I want a solution that isn't quite so ridiculous.

This is the closest I've gotten so far to a real solution:

def myperms(elem, mylist):
    for i in range(len(elem)-1,-1,-1):
        while (elem[i] + 1) < ord:
            elem = list(elem)
            elem[i] += 1
            if elem not in mylist:
                mylist.append(elem)
        if (elem[i] + 1) >= ord: 
            elem = list(elem)
            elem[i] = 0
    return mylist

Num = 3
ord = 2

TotsNum = ord**Num

mylist = []
elem = [0,]*Num
mylist.append(elem)

print(myperms(elem, mylist))

But this only gives:

[[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0]]

I've tried calling the function within itself (recursion), but I haven't been able to figure out how to do it properly. Does anyone have any ideas about how to solve it recursively? Thank you!

permutation recursion python
2 Answers

Let's use a recursive solution:

def get_seq(ord, num):
    val = [0]*num
    N = num
    def recurse(ord, num):
        for i in range(ord):
            val[N - num] = i
            if num > 1:
                yield from recurse(ord, num-1)
            else:
                yield val[:]
    return recurse(ord, num)

print(list(get_seq(2, 4)))

Output:

[[0, 0, 0, 0],
 [0, 0, 0, 1],
 [0, 0, 1, 0],
 [0, 0, 1, 1],
 [0, 1, 0, 0],
 [0, 1, 0, 1],
 [0, 1, 1, 0],
 [0, 1, 1, 1],
 [1, 0, 0, 0],
 [1, 0, 0, 1],
 [1, 0, 1, 0],
 [1, 0, 1, 1],
 [1, 1, 0, 0],
 [1, 1, 0, 1],
 [1, 1, 1, 0],
 [1, 1, 1, 1]]

For other inputs:

>>> list(get_seq(3, 2))
[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
user_54317910

Use binary, which consists of 0s and 1s.

n = 4
all_permutations = []
for i in range(2**n):
    permutation = []
    string = bin(i)
    string = string.split("0b")[1]
    while len(string) != n:
        string = f"0{string}"
    
    for i in string:
        permutation.append(int(i))

    all_permutations.append(permutation)

print(all_permutations)
user_145360290
Related