Python - itertools.product不使用元素多次

Question

我有一个列表列表,我想复制itertools.product()多次不使用任何元素的效果.

>>> list = [['A', 'B'], ['C', 'D'], ['A', 'B']]
>>> [''.join(e) for e in itertools.product(*list)]
['ACA', 'ACB', 'ADA', 'ADB', 'BCA', 'BCB', 'BDA', 'BDB']
>>> # Desired output: ['ACB', 'ADB', 'BCA', 'BDA']

我需要使用它的列表太大,无法计算itertools.product和删除不需要的元素.(250亿个排列itertools.product,而我想要的输出只有~500,000).优选地,答案是可迭代的.

编辑:我知道"产品"是我需要的错误术语,但我很难找到我正在寻找的词.

Edit2:这是我希望执行此操作的列表:

[['A', 'H', 'L'], ['X', 'B', 'I'], ['Q', 'C', 'V'], ['D', 'N'], ['E', 'F'], ['E', 'F'], ['G'], ['A', 'H', 'L'], ['X', 'B', 'I'], ['W', 'U', 'J', 'K', 'M'], ['W', 'U', 'J', 'K', 'M'], ['A', 'H', 'L'], ['W', 'U', 'J', 'K', 'M'], ['D', 'N'], ['P', 'O', 'T'], ['P', 'O', 'T'], ['Q', 'C', 'V'], ['R'], ['S'], ['P', 'O', 'T'], ['W', 'U', 'J', 'K', 'M'], ['Q', 'C', 'V'], ['W', 'U', 'J', 'K', 'M'], ['X', 'B', 'I']]

Answer 1

一个简单的基于堆栈的实现：

def product1(l): return product1_(l,0,[])
def product1_(l,i,buf):
  if i==len(l): yield buf
  else:
    for x in l[i]:
      if x not in buf:
        buf.append(x)
        yield from product1_(l,i+1,buf)
        buf.pop()

这比 Patrick Haugh 的答案要慢一些（我的测试用例需要 18 秒），但它以可预测的顺序给出结果。

请注意，您必须在生成“它们”时处理这些值，因为它们都是相同的列表buf；您可以编写yield tuple(buf)或yield "".join(buf)生成单独的“熟”值（花费不到一秒的时间）。

如果值是字母，则可以使用“位掩码”列表来实现碰撞测试，这会将时间减少到大约 13 秒（但使用 aset也同样快）。其他可能的优化包括首先处理符合条件元素较少的列表，以减少回溯；这可以将这种情况缩短至 11 秒。