如何为按不同大小分组的元素列表生成所有可能的组合？

Question

我正在尝试创建一种算法，该算法将 return 元素列表中的所有可能组合（本例中为水果）。挑战在于 元素可以按不同的大小进行分组 并且 结果列表中的元素数量必须等于 n，其中 n 是 列表大小 。简而言之，所有元素都必须在最终列表中。

这是一个例子：

fruits = ['Apple', 'Orange', 'Banana', 'Watermelon']

我们可以快速找到从size 0到n的所有组合，如下所示：

from itertools import combinations

fruits = ['Apple', 'Orange', 'Banana', 'Watermelon']
for L in range(0, len(fruits) + 1):
    for subset in combinations(fruits, L):
        print(subset)

结果：

()
('Apple',)
('Orange',)
('Banana',)
('Watermelon',)
('Apple', 'Orange')
('Apple', 'Banana')
('Apple', 'Watermelon')
('Orange', 'Banana')
('Orange', 'Watermelon')
('Banana', 'Watermelon')
('Apple', 'Orange', 'Banana')
('Apple', 'Orange', 'Watermelon')
('Apple', 'Banana', 'Watermelon')
('Orange', 'Banana', 'Watermelon')
('Apple', 'Orange', 'Banana', 'Watermelon')

但是，我正在寻找的是不同的，因为所有元素都必须存在。示例：

('Apple',) ('Orange',) ('Banana',) ('Watermelon',) is valid (1),(1),(1),(1)
('Apple',) ('Orange',) ('Banana', 'Watermelon') is valid (1),(1),(2)
('Apple',) ('Banana',) ('Orange', 'Watermelon') is valid (1),(1),(2)
('Apple',) ('Watermelon',) ('Orange', 'Banana') is valid (1),(1),(2)
('Apple',) ('Orange', 'Banana', 'Watermelon') is valid (1),(3)
...
('Apple', 'Orange') ('Banana', 'Watermelon') is valid (2),(2)
('Apple', 'Orange', 'Banana', 'Watermelon') is valid (4)

在 Python 中是否有生成此内容的简单方法？

Answer 1

您应该看看应该适合您需要的 more-itertools library. And more particularly to the set_partitions 方法。

from more-itertools import set_partitions

fruits = ['Apple', 'Orange', 'Banana', 'Watermelon']

for itm in set_partitions(fruits)):
    print(itm)

输出结果为：

[['Apple', 'Orange', 'Banana', 'Watermelon']]
[['Apple'], ['Orange', 'Banana', 'Watermelon']]
[['Apple', 'Orange'], ['Banana', 'Watermelon']]
[['Orange'], ['Apple', 'Banana', 'Watermelon']]
[['Apple', 'Orange', 'Banana'], ['Watermelon']]
[['Orange', 'Banana'], ['Apple', 'Watermelon']]
[['Apple', 'Banana'], ['Orange', 'Watermelon']]
[['Banana'], ['Apple', 'Orange', 'Watermelon']]
[['Apple'], ['Orange'], ['Banana', 'Watermelon']]
[['Apple'], ['Orange', 'Banana'], ['Watermelon']]
[['Apple'], ['Banana'], ['Orange', 'Watermelon']]
[['Apple', 'Orange'], ['Banana'], ['Watermelon']]
[['Orange'], ['Apple', 'Banana'], ['Watermelon']]
[['Orange'], ['Banana'], ['Apple', 'Watermelon']]
[['Apple'], ['Orange'], ['Banana'], ['Watermelon']]

编辑：

并且如果您希望所有可能的组合，如果您重新排序您的原始列表，您可以将以前的方法与 permutations 方法结合使用 itertools 类似：

import itertools
from more_itertools import set_partitions

fruits = ['Apple', 'Orange', 'Banana', 'Watermelon']
output = list()

for x in itertools.permutations(fruits):
    output += list(set_partitions(x))

如何为按不同大小分组的元素列表生成所有可能的组合？

How to generate all the possible combinations for a list of elements grouped in different sizes?

python

combinations

编辑：