python - 寻找组合的组合

Question

假设我们有一个列表列表：

list = [[a],[b],[c],[d],[e],[f],[g],[h]]

现在我希望生成 2 乘 3 的所有可能组合，因此一种可能的组合是：

[[[a],[b],[c]], [[d],[e],[f]]]

另一个是：

[[[g],[h],[c]], [[d],[e],[f]]]

或者

[[[a],[b],[f]], [[d],[e],[c]]]

顺序在任何级别都无关紧要。但是，元素不得重复，这意味着以下列表不正确，不应生成：

[[[a],[b],[f]], [[a],[e],[f]]]

相似地

 [[a,b,c], [e,f,c]]   and   [[e,f,c], [a,b,c]]

将是同一件事，并且应该只出现一次。

我已经炸了很多神经细胞，但无法产生有效的解决方案。我正在使用 Python 来解决这个问题。

标签： pythoncombinatorics

Answer 1

You can use a recursive generator function:

lst = [['a'],['b'],['c'],['d'],['e'],['f'],['g'],['h']]
x = 3
def combos(lst, n, c = []):
   if sum(map(len, c)) == (l:=len(lst))-(l%x):
      yield c
   else:
      for i in filter(lambda x:not any(x in i for i in c), lst):
         if not c or len(c[-1]) == n:
             yield from combos(lst, n, c+[[i]])
         else:
             yield from combos(lst, n, [*c[:-1], c[-1]+[i]])

result = list(combos(lst, x))
print(result[:10])

Output:

[[['a'], ['b'], ['c']], [['d'], ['e'], ['f']]]
[[['a'], ['b'], ['c']], [['d'], ['e'], ['g']]]
[[['a'], ['b'], ['c']], [['d'], ['e'], ['h']]]
[[['a'], ['b'], ['c']], [['d'], ['f'], ['e']]]
[[['a'], ['b'], ['c']], [['d'], ['f'], ['g']]]
[[['a'], ['b'], ['c']], [['d'], ['f'], ['h']]]
[[['a'], ['b'], ['c']], [['d'], ['g'], ['e']]]
[[['a'], ['b'], ['c']], [['d'], ['g'], ['f']]]
[[['a'], ['b'], ['c']], [['d'], ['g'], ['h']]]
[[['a'], ['b'], ['c']], [['d'], ['h'], ['e']]]
...