检查两个嵌套列表在替换时是否等效 [英] Check if two nested lists are equivalent upon substitution

问题描述

在某些情况下，我试图列举在计算 Banzhaf时可能发生的独特情况的数量当没有独裁者并且有四个或五个获胜联盟时，四个球员的力量指数。

For some context, I'm trying to enumerate the number of unique situations that can occur when calculating the Banzhaf power indices for four players, when there is no dictator and there are either four or five winning coalitions.

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

I am using the following code to generate a set of lists that I want to iterate over.

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

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

However, two lists in this set shouldn't be considered unique if they are equivalent under remapping.

以以下列表为例：

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

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

If each element 2 is renamed to 3 and vice-versa, we would get:

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

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

The order in each sub-list is unimportant, and the order of the sub-lists is also un-important. Thus, the swapped list can be rewritten as:

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

有4个值，所以有P（ 4,4）= 24可能发生的重新映射（包括琐碎的映射）。

There are 4 values, so there are P(4,4)=24 possible remappings that could occur (including the trivial mapping).

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

Is there any way to check this easily? Or, even better, is there are way to avoid generating these lists to begin with?

我什至不确定如何将第一个列表转换为第二个列表（但可以从那里强行使用）。另外，我不限于数据类型（在某种程度上），使用 frozenset 也可以。

I'm not even sure how I would go about transforming the first list into the second list (but could brute force it from there). Also, I'm not restricted to data type (to a certain extent) and using frozenset would be fine.

编辑： tobias_k提供的解决方案回答了检查问题，但是，正如评论中指出的那样，我认为我对这个问题的解决方法不正确。

The solution offered by tobias_k answers the "checking" question but, as noted in the comments, I think I have the wrong approach to this problem.

推荐答案

这可能还不是完整的解决方案，但是它可能会向您显示进一步研究的方向。

This is probably no complete solution yet, but it might show you a direction to investigate further.

您可以将每个元素映射到与拓扑有关的某些特征，以及它们如何与其他元素连接。您必须小心，不要考虑集合中的顺序，也不要考虑元素本身。例如，您可以考虑元素出现的频率，元素出现的大小组以及类似的内容。将这些度量标准组合到键函数中，按该键对元素进行排序，然后按该顺序为其分配新名称。

You could map each element to some characteristics concerning the "topology", how it is "connected" with other elements. You have to be careful not to take the ordering in the sets into account, or -- obviously -- the element itself. You could, for example, consider how often the element appears, in what sized groups it appears, and something like this. Combine those metrics to a key function, sort the elements by that key, and assign them new names in that order.

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

这会将您的两个示例列表映射到相同的标准化列表：

This maps your two example lists to the same "normalized" list:

>>> 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。我不知道这是不是很小，但这看起来是一个不错的开始。

When applied to all the lists, it gets the count down from 330 to 36. I don't know if this is minimal, but it looks like a good start.

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

这篇关于检查两个嵌套列表在替换时是否等效的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！