检查两个嵌套列表在替换时是否等效

Question

对于某些情况，我试图列举在计算 Banzhaf power indices 四名玩家时可能发生的独特情况的数量，当没有独裁者并且有四个或五个获胜联盟时。

我正在使用以下代码生成一组我想要迭代的列表。

from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(map(list, combinations(s, r)) for r in range(2, len(s)+1))

def superpowerset(iterable):
    s = powerset(iterable)
    return chain.from_iterable(map(list, combinations(s, r)) for r in range(4, 6))

set_of_lists = superpowerset([1,2,3,4])

但是，如果此集合中的两个列表在重新映射下等效，则它们不应被视为唯一。

以下面的列表为例：

[[1, 2], [1, 3], [2, 3], [1, 2, 4]]

如果每个元素 2 重命名为 3，反之亦然，我们将得到：

[[1, 3], [1, 2], [3, 2], [1, 3, 4]]

每个子列表中的顺序并不重要，子列表的顺序也不重要。因此，交换列表可以重写为：

[[1, 2], [1, 3], [2, 3], [1, 3, 4]]

有 4 个值，因此可能会发生 P(4,4)=24 种可能的重新映射（包括普通映射）。

有什么方法可以轻松检查吗？或者，更好的是，是否有办法避免生成这些列表？

我什至不确定如何将第一个列表转换为第二个列表（但可以从那里强制执行）。另外，我不受数据类型的限制（在一定程度上）并且使用 frozenset 就可以了。

编辑： tobias_k 提供的解决方案回答了 "checking" 问题，但是，如评论中所述，我认为我的方法是错误的这个问题。

Answer 1

这可能还不是完整的解决方案，但它可能会为您指明进一步调查的方向。

您可以将每个元素映射到与 "topology" 相关的某些特征，以及 "connected" 与其他元素的关系。您必须小心不要考虑集合中的顺序，或者 - 显然 - 元素本身。例如，您可以考虑元素出现的频率、它出现在多大的组中，以及诸如此类的事情。将这些指标组合成一个键函数，按该键对元素进行排序，然后按该顺序为它们分配新名称。

def normalize(lists):
    items = set(x for y in lists for x in y)
    counter = itertools.count()
    sorter = lambda x: sorted(len(y) for y in lists if x in y)
    mapping = {k: next(counter) for k in sorted(items, key=sorter)}
    return tuple(sorted(tuple(sorted(mapping[x] for x in y)) for y in lists))

这会将您的两个示例列表映射到同一个 "normalized" 列表：

>>> normalize([[1, 2], [1, 3], [2, 3], [1, 2, 4]])
((0, 1), (0, 2), (1, 2), (1, 2, 3))
>>> normalize([[1, 3], [1, 2], [3, 2], [1, 3, 4]])
((0, 1), (0, 2), (1, 2), (1, 2, 3))

当应用于所有列表时，它会将计数从 330 减少到 36。我不知道这是否是最小的，但它看起来是一个好的开始。

>>> normalized = set(map(normalize, set_of_lists))
>>> len(normalized)
36

检查两个嵌套列表在替换时是否等效

Check if two nested lists are equivalent upon substitution

python

algorithm

combinatorics

itertools