如何枚举组合过滤重复

Question

我有一个可能的选择列表：[[1], [2, 4], [4], [5, 6, 2], [5, 3]]。

我想列出所有组合，从每个子列表中最多获取一个元素，而不重复元素。

所以这[1, 2, 4, 5, 3]是一个有效的选择。但[1, 4, 4, 5, 3]事实并非如此。我允许不在任何子列表中做出选择，因此[1,4, None,5,3]是有效的，如[1, None, None, None, None]、 和中所示[None, None, None, None, None]。

我不能简单地枚举所有组合，然后过滤掉我不想要的组合，因为对于大量可能的选择，它很快就会在计算上变得不可行（我正在我的项目中查看 25^25 个最大组合）。

编辑：我还会对结果应用一些附加标准，例如过滤以不超过选择阈值None，或者按最少组合的顺序对结果组合列表进行排序None。

编辑：真实案例的详细信息：我想将其应用于 25 个子列表的列表，每个子列表可以有 1-25 个元素。实际上，每个子列表最多有 15 个元素，平均 2-4 个。

那么简单的过滤解决方案list(itertools.product(*choices))就出来了。

我可能还希望将其他过滤条件添加到组合列表中，因此理想情况下我可以预先过滤这些条件。

我尝试递归地构建一棵树，其中根节点具有完整的选择列表，子节点做出第一个选择[1]，并且具有更新的选择列表，其中“1”从所有列表中删除[1:]选择。

但努力实现递归。

您能帮助我采取其他方法吗？

Answer 1

以最少的内存使用量生成所有有效输出的另一种方法是迭代元素而不是列表。使用深度优先搜索，以便您从一开始就只生成有效的输出。这意味着我们需要在 DFS 的每个级别中跟踪三件事：当前要添加的元素、已使用的列表以及我们使用先前列表的顺序。

为了帮助我们的搜索，我们通过将每个元素映射到它可能位于的一组可能列表来预处理选择，这创建了一种问题的双重版本。这也会以大致“最大非空选择优先”的顺序生成列表。

由于您已指定唯一元素的数量 N 等于列表的数量，因此这种方法可以及时运行O(N * |output|)，并且我们到处都使用生成器来节省内存。

import collections
from typing import Dict, Generator, List, Optional, Set

choices = [[1], [2, 4], [4], [5, 6, 2], [5, 3]]
element_to_containing_lists: Dict[int, Set[int]] = collections.defaultdict(set)

for i, choice_list in enumerate(choices):
    for x in choice_list:
        element_to_containing_lists[x].add(i)

all_unique_elements = sorted(element_to_containing_lists)


def dfs(used_list_indices: Set[int],
        next_element_index: int,
        used_list_ordered_indices: List[Optional[int]]) -> Generator[List[Optional[int]]]:
    if next_element_index == len(all_unique_elements):
        yield used_list_ordered_indices
    else:
        # If we use the element, find an unused list index
        for possible_list_to_use in element_to_containing_lists[
                                        all_unique_elements[next_element_index]] - used_list_indices:
            yield from dfs(used_list_indices | {possible_list_to_use},
                           next_element_index + 1,
                           used_list_ordered_indices + [possible_list_to_use])

        # If we don't use the element: Add None as a sentinel value
        yield from dfs(used_list_indices,
                       next_element_index + 1,
                       used_list_ordered_indices + [None])


for element_to_used_list in dfs(set(), 0, []):
    list_to_chosen_element = ['N'] * len(choices)
    for x, y in zip(all_unique_elements, element_to_used_list):
        if y is not None:
            list_to_chosen_element[y] = x
    print(*list_to_chosen_element, sep='  ')

输出的前 10 行：

1  2  4  5  3
1  2  4  6  3
1  2  4  N  3
1  2  N  5  3
1  2  N  6  3
1  2  N  N  3
1  2  4  5  N
1  2  4  6  5
1  2  4  N  5

这可以O(|output|)通过使用“已用列表”的位掩码而不是一组索引来优化以及时运行。

Answer 2

不要将结果变成列表。product是一个发电机。利用这一点来发挥你的优势。filter也是一个发电机。通过这种方式，您只能在内存中保存一个组合。有时单个输出product会在你看不到的情况下被内部丢弃，但它不会占用任何额外的空间。

def criterion(x):
    k = [i for i in x if i is not None]
    return len(k) == len(set(k))

choices = [[1], [2, 4], [4], [5, 6, 2], [5, 3]]
for c in choices:
    c.append(None)
filter(criterion, product(*choices))