Pythonitertools.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亿排列，而我想要的输出只有~500000）。最好是一个可以接受的答案。在

编辑：我知道“产品”这个词用在我需要的词上是错误的，但我正在努力寻找我要找的词。在

编辑2:这是我希望对其执行此操作的列表：

^{pr2}$

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)或{}来生成单独的“熟”值（代价不到额外的一秒钟）。在

如果值是字母，您可以使用“bitmask”列表来实现碰撞测试，这将时间缩短到大约13秒（但是使用set同样快）。其他可能的优化包括首先处理具有较少合格元素的列表，以减少回溯；这可以将这种情况减少到11秒

Answer 2

你的具体案件有一个有趣的性质。如果我们把它安排在一个计数器中，我们会看到每个列表出现的次数与它的条目相同：

Counter({('A', 'H', 'L'): 3,
         ('D', 'N'): 2,
         ('E', 'F'): 2,
         ('G',): 1,
         ('P', 'O', 'T'): 3,
         ('Q', 'C', 'V'): 3,
         ('R',): 1,
         ('S',): 1,
         ('W', 'U', 'J', 'K', 'M'): 5,
         ('X', 'B', 'I'): 3})

换句话说，忽略顺序，你想要的序列就是列表排列的笛卡尔积。假设您的列表名为l。然后我们可以将子列表的所有排列组合起来，并得到它们的乘积：

^{pr2}$

permutation_products的元素类似于：

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

我们必须把它恢复到正确的顺序。{我们的排列叫做{cd3}。对于列表的每个子列表，我们必须找到perm的正确元素，然后取排列中的下一个字母。我们可以做一本字典：

perm_dict = {frozenset(p): list(p) for p in perm}

然后，为了构造一个单一排列，我们有：

s = "".join([perm_dict[frozenset(i)].pop() for i in l])

我们可以把所有这些结合成一个发电机：

def permute_list(l):
    c = set(tuple(i) for i in l)
    permutations = [list(itertools.permutations(i)) for i in c]
    permutation_products = itertools.product(*permutations)
    for perm in permutation_products:
        perm_dict = {frozenset(p): list(p) for p in perm}
        yield "".join([perm_dict[frozenset(i)].pop() for i in l])

Answer 3

test1 = [['A', 'B'], ['C', 'D'], ['A', 'B']]                                                                                           
test2 = [['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']]


def prod(curr, *others):
    if not others:
        for x in curr:
            yield {x} # (x,) for tuples
    else:
        for o in prod(*others):
            for c in curr:
                if c not in o:
                    yield {c, *o} # (c, *o) for tuples

print([''.join(x) for x in prod(*test1)])
# ['ABC', 'ABD', 'ABC', 'ABD'] 
print(sum(1 for x in prod(*test2)))
# 622080

较长的输入在我的机器上运行大约需要5秒钟。我使用sets来传递值，因为在成员资格检查时，它们比元组或列表更有效。如果需要的话，你可以使用元组，只不过速度会慢一些。在

需要思考的几个问题：顺序重要吗？当我们无法使用当前列表中的项目（因为它们都已被使用）时，您希望发生什么？在