从包含不同长度子列表的列表构造所有组合

Question

我想解决以下问题：给定一个包含不同长度的子列表的列表，比如L = [ [ 'a', 'b' ], [ 'c' ], [ 'd', 'e', 'f' ] ]，构造所有的组合，每个子列表只包含一个元素。所以[ 'a', 'c', 'd' ]是正确的组合，但不是[ 'a', 'b', 'e' ]。子列表长度的乘积有多少组合就有多少，这里是6个组合，简而言之（顺序不重要）：cda, cdb, cea, ceb, cfa, cfb

这个想法是采取一个任意子列表，但不是一个单一的，采取补充和创造尽可能多的新的子列表从补充和一个成员所选择的子列表所决定的子列表长度。现在继续获取另一个长度大于1的子列表，并递归地执行此操作，直到所有子列表只包含单例。这种递归必须在构造完所有寻求的组合之后结束。代码如下：

def break_bipartite_chain( var_list ):
    print('a')
    bbc = []
    def recursive_break( var_list ):
        print('b')
        bipartite_chain = sorted( var_list , key=len , reverse=True )
        LC = len( bipartite_chain )
        LCF = len( bipartite_chain[ 0 ] ) 
        complement_chain = []
        for i in range( 0, LCF ):
            complement_chain.append( bipartite_chain[ 1 : ] )
        if LCF == 1:
            print('c')
            bbc.append( bipartite_chain )
            return None
        else:
            print('d')
            for i in range( 0 , LCF ):
                complement_chain[i].append([ bipartite_chain[ 0 ][ i ] ])
        LCC = len( complement_chain )
        for i in range( 0 , LCC ):
            print('e')
            recursive_break( complement_chain[ i ] )
        return None
    bbc.append( recursive_break( var_list ) )
    return bbc[:-1]

现在，代码可以正常工作并做它应该做的事情（至少在我尝试过的示例中是这样），但是我仍然不完全满意它，因为我是一个相对的python新手，所以我建议您发表任何评论，包括样式，并将重点放在以下问题上：

1. 它只会因为if部分中最内部的“return”而起作用。我不知道当我去掉它的时候会发生什么，但是它给了我一个 错误代码“IndexError:列表索引超出范围”？我想用这种风格离开if部分并不是一个很好的解决方案，但是我在这个论坛上发现了一些其他人，他们建议使用一个“return”命令来过早地打破这种说法。有更好的解决方案吗

2. 最中间的“return”似乎是不必要的，但不管我是否编写它（在这两种情况下都有效），它都会编写一个“None”，我通过在最外层的return中切片来删除它。有没有什么办法可以抑制这种“无”呢

3. 虽然它工作，我仍然不确定递归操作。我一步一步地跟踪上面给出的示例（这就是为什么会有print命令），这是合乎逻辑的。我可以预测解决方案的顺序，他们同意了。但是递归经常看起来很神奇。有更清洁的解决方案吗

4. 第一个for循环可能没有必要，我尝试了两种方法：（I）不使用补码的乘法（稍后在第二个for循环中使用complement\u chain.append），或者（ii）使用bipartite_chain[1:]*LCF，要么根本不起作用（第一种情况），要么产生一个奇怪的行为，在这种情况下，我想附加的条目也出现了LCF次（第二种情况）

最后，我想可能有更好的解决办法？或者至少是一些需要改进的小事情

谢谢你的建议

Answer 1

你可以用itertools.product来做这个

>>> list(itertools.product(*L))
[('a', 'c', 'd'), ('a', 'c', 'e'), ('a', 'c', 'f'), ('b', 'c', 'd'), ('b', 'c', 'e'), ('b', 'c', 'f')]

因为你实际上是想构造Cartesian product

Answer 2

您可以使用生成器创建一个更简单的递归函数。此外，似乎在您的解决方案中考虑了[['a', 'b'], ['c'], ['d', 'e', 'f']]子列表的所有可能顺序，因此，可以实现一个额外的递归方法来查找l的所有可能位置：

l = [['a', 'b'], ['c'], ['d', 'e', 'f']]
from collections import Counter
def placement(d, _c = []):
  if len(_c) == len(d):
    yield _c
  else:
    for i in d:
      _c1, _c2 = Counter(map(tuple, d)), Counter(map(tuple, _c))
      if _c2[tuple(i)] < _c1[tuple(i)]:
         yield from placement(d, _c+[i])

def combos(d, _c = []):
  if len(_c) == len(l):
    yield _c
  else:
    for i in d[0]:
      yield from combos(d[1:], _c+[i])

final_results = [''.join(i) for b in placement(l) for i in combos(b)]

输出：

['acd', 'ace', 'acf', 'bcd', 'bce', 'bcf', 'adc', 'aec', 'afc', 'bdc', 'bec', 'bfc', 'cad', 'cae', 'caf', 'cbd', 'cbe', 'cbf', 'cda', 'cdb', 'cea', 'ceb', 'cfa', 'cfb', 'dac', 'dbc', 'eac', 'ebc', 'fac', 'fbc', 'dca', 'dcb', 'eca', 'ecb', 'fca', 'fcb']