查找组合的组合

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来解决这个问题。

Answer 1

您可以使用递归生成器函数：

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

输出：

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

Answer 2

itertools.permutations-function就是您要找的东西！你的问题实际上可以通过创建6个元素的所有排列，然后简单地将所有这些排列拆分为两个列表来解决。

这段代码应该可以解决你的问题：

>>> from itertools import permutations
>>> lst = [['a'],['b'],['c'],['d'],['e'],['f'],['g'],['h']]

>>> [(x[:3], x[3:]) for x in permutations(lst, 6)]
[((['a'], ['b'], ['c']), (['d'], ['e'], ['f'])),
 ((['a'], ['b'], ['c']), (['d'], ['e'], ['g'])),
 ((['a'], ['b'], ['c']), (['d'], ['e'], ['h'])),
 ((['a'], ['b'], ['c']), (['d'], ['f'], ['g'])),
 ((['a'], ['b'], ['c']), (['d'], ['f'], ['h'])),
 ((['a'], ['b'], ['c']), (['d'], ['g'], ['h'])),
 ...

它不仅简单，而且速度也很快：

>>> %timeit [(x[:3], x[3:]) for x in permutations(lst, 6)]
7.32 ms ± 94.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Answer 3

itertools是一个很受欢迎的库，可以从这些类型的问题中减轻一些精神负担。

一个利用itertools的解决方案(请检查这是否适用于您的用例，以防您忘记提到排序需求)：

import itertools
l = [['a'],['b'],['c'],['d'],['e'],['f'],['g'],['h']]
threecombs = list(itertools.combinations(l, r=3))
twocombs = []
for comb1, comb2 in itertools.product(threecombs, threecombs):
   if all(c not in comb2 for c in comb1):
       twocombs.append([list(comb1), list(comb2)])

如果你的列表很大，可以通过不将三个your转换成一个列表来加快速度，但是如果你愿意的话，我会把它留给你，因为你的问题表明你正在使用列表，而不是生成器。