如何递归地找到可变数量的 0 和 1 的所有排列（不使用 itertools 或随机）？

Question

我正在尝试为可变数量的位置生成一定数量的数字（例如 0 和 1）的所有排列。我将数字的数量称为 ord（例如 ord=2 仅表示 0 和 1；ord=3 表示 0、1 和 2）和位置的数量 Num。因此排列数为ord**Num.

注意：我不想使用 itertools 或任何其他类型的内置函数。我问这个是出于好奇，而不仅仅是想找到解决方案。

对于 ord=2 和 Num=3，输出按任何顺序应为：

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

这可以通过以下方式完成：

ord = 2 
mylist = []

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

对于ord = 2和Num = 4，输出应该是：

[[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 循环：

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])

一个明显的解决方案是将 0 和 1 随机添加到长度为 Num 的列表中，然后如果该列表尚未添加到 mylist 中则接受该列表，但我想要一个不是那么荒谬的解决方案。

这是迄今为止我最接近真正的解决方案：

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))

但这只会给出：

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

我试过在其自身内部调用该函数（递归），但我一直无法弄清楚如何正确地调用它。有没有人对如何递归解决它有任何想法？谢谢！

Answer 1

使用二进制，由 0 和 1 组成。

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)

Answer 2

让我们使用递归解决方案：

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)))

输出：

[[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]]

对于其他输入：

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

如何递归地找到可变数量的 0 和 1 的所有排列（不使用 itertools 或随机）？

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

python

recursion

permutation