python 中数组的所有排列

Question

我有一个数组。我想从该数组生成所有排列，包括单个元素、重复元素、更改顺序等。例如，假设我有这个数组：

arr = ['A', 'B', 'C']

如果我通过这样做来使用 itertools 模块：

from itertools import permutations
perms = [''.join(p) for p in permutations(['A','B','C'])]
print(perms)

或者像这样使用循环：

def permutations(head, tail=''):
if len(head) == 0:
    print(tail)
else:
    for i in range(len(head)):
        permutations(head[:i] + head[i+1:], tail + head[i])
        
arr= ['A', 'B', 'C']
permutations(arr)

我只得到：

['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']

但我想要的是：

['A', 'B', 'C', 
 'AA', 'AB', 'AC', 'BB', 'BA', 'BC', 'CA', 'CB', 'CC', 
 'AAA', 'AAB', 'AAC', 'ABA', 'ABB', 'ACA', 'ACC', 'BBB', 'BAA', 'BAB', 'BAC', 'CCC', 'CAA', 'CCA'.]

结果是给定数组的所有排列。由于数组是3个元素，而且所有元素都可以重复，所以生成3^3（27）种方式。我知道一定有办法做到这一点，但我不太理解正确的逻辑。

Answer 1

一个生成器，可以生成您描述的所有序列（如果您尝试耗尽它，它的长度是无限的）：

from itertools import product


def sequence(xs):
    n = 1
    while True:
        yield from (product(xs, repeat=n))
        n += 1


# example use: print first 100 elements from the sequence
s = sequence('ABC')
for _ in range(100):
    print(next(s))

输出：

('A',)
('B',)
('C',)
('A', 'A')
('A', 'B')
('A', 'C')
('B', 'A')
('B', 'B')
('B', 'C')
('C', 'A')
('C', 'B')
('C', 'C')
('A', 'A', 'A')
('A', 'A', 'B')
('A', 'A', 'C')
('A', 'B', 'A')
...

当然，如果你不需要元组，而是字符串，只需将 next(s) 替换为 ''.join(next(s))，即：

    print(''.join(next(s)))

如果您不希望序列超过原始集合的长度：

from itertools import product


def sequence(xs):
    n = 1
    while n <= len(xs):
        yield from (product(xs, repeat=n))
        n += 1


for element in sequence('ABC'):
    print(''.join(element))

当然，在这种有限的情况下，这也可以：

from itertools import product

xs = 'ABC'
for s in (''.join(x) for n in range(len(xs)) for x in product(xs, repeat=n+1)):
    print(s)

编辑：在评论中，OP 要求对 yield from (product(xs, repeat=n)) 部分进行解释。

product() 是 itertools 中的一个函数，它生成可迭代对象的笛卡尔积，这是一种奇特的方式，可以说您从第一个可迭代对象中获得所有可能的元素组合，其中元素来自第二个等等

尝试一下以更好地感受它，例如：

list(product([1, 2], [3, 4])) == [(1, 3), (1, 4), (2, 3), (2, 4)]

如果你将一个可迭代对象的乘积与自身相乘，也会发生同样的情况，例如：

list(product('AB', 'AB')) == [('A', 'A'), ('A', 'B'), ('B', 'A'), ('B', 'B')]

请注意，我在这里一直用 list() 调用 product()，那是因为 product() returns 一个生成器并将生成器传递给 list() 耗尽将生成器放入列表中，以供打印。

product() 的最后一步是你还可以给它一个可选的 repeat 参数，它告诉 product() 做同样的事情，但只是重复某个特定的可迭代对象次数。例如：

list(product('AB', repeat=2)) == [('A', 'A'), ('A', 'B'), ('B', 'A'), ('B', 'B')]

因此，如果您从 n=1 开始并不断耗尽它，那么您可以看到调用 product(xs, repeat=n) 将如何生成您之后的所有序列 n。

最后，yield from 是一种在您自己的生成器中一次从另一个生成器生成结果的方法。例如，yield from some_gen 等同于：

for x in some_gen:
    yield x

因此，yield from (product(xs, repeat=n)) 等同于：

for p in (product(xs, repeat=n)):
    yield p

python 中数组的所有排列

All permutations of an array in python

python

arrays

permutation