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 计算并移除不必要的元素太耗费时间了，因为我的列表过于庞大（25亿个排列组合）。我只需要 ~500,000 个元素。希望能够得到一个可迭代的答案。

注：我知道“product”是错误的术语，但我找不到我所需的单词。

注2：这是我想执行此操作的列表。

[['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']]

- user72528

---

你不需要使用 product，你需要的不是笛卡尔积。 - Olivier Melançon

@Olivier 我知道。请看编辑。我应该用什么词代替？ - user72528

你需要它用于更一般的情况还是仅限于这个特定的输入？ - Olivier Melançon

@Olivier 如果“这个特定的输入”是指我的丑陋需求，那么这就是我真正需要的，但如果可能的话，我更喜欢一个通用情况。我将编辑需要执行此操作的列表。 - user72528

Answer 1

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

在我的机器上，较长的输入大约需要五秒钟才能运行。我使用set来传递值，因为当涉及成员资格检查时，它们比元组或列表更有效率。如果必要，您可以使用元组，但速度会慢一些。

一些需要考虑的问题：顺序是否重要？当我们无法使用当前列表中的项目（因为它们已全部被使用）时，您希望发生什么？

- Patrick Haugh

---

如果所有元素都已被使用，则您将得不到任何结果。例如，如果您从 [AB，BC，AB，XY] 中选择 A 和 B，则会得到空结果。如果这是不可避免的（例如，[AB，AB，AB]），则整个结果为空。 - Davis Herring

Answer 2

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

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)来生成单独的“处理过”的值（代价不到1秒）。

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

- Davis Herring

Answer 3

你的特殊情况具有一个有趣的属性。如果我们按计数器排列它，我们会看到每个列表出现的次数与其条目相同：

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。然后我们可以组装一个子列表的所有排列的列表，并取它们的乘积。

c = set(tuple(i) for i in l)
permutations = [list(itertools.permutations(i)) for i in c]
permutation_products = itertools.products(*permutations)

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

我们需要将它恢复到正确的顺序。假设我们的排列被称为perm。对于列表的每个子列表，我们必须定位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])

- hoyland

---

如果按照原文所写，这个程序需要24秒才能完成；但是如果你将排列作为生成器而不将其转换为列表，并提前创建一个frozenset列表，则只需要14秒即可完成。 - hoyland