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 并删除不需要的元素。 (来自 itertools.product 的 250 亿个排列，而我想要的输出只有约 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) 来生成单独的“cooked”值(花费不到一秒的额外时间)。

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