寻找组合的组合

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

^{}-函数就是您要寻找的！您的问题实际上可以通过创建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 2

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

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

如果您的列表很大，可以通过不将threecombs转换为列表来加快速度，但是如果您愿意这样做，我将把它留给您，因为您的问题表明您使用的是列表，而不是生成器