检查两个嵌套列表在替换后是否等价

Question

检查两个嵌套列表在替换后是否等价

pythonalgorithmcombinatoricspython-itertools

4

为了更好地理解，我正在尝试枚举在计算四个玩家的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提供的解决方案回答了“检查”问题，但正如评论中所指出的那样，我认为我对这个问题的方法是错误的。

- Jared Goguen

2

我认为你可以尝试找到每个集合的“标准化”形式，然后将它们全部放入一个集合中。当然，棘手的部分是使标准化形式唯一。你可以对集合中的数字进行排序，例如将出现频率最高的数字设为1，接下来是2，以此类推，并使用一些类似的指标来打破平局。 - tobias_k

期望清单上有什么？那些是获胜联盟还是什么？ - Tony Babarino

如果您想比较无序的列表，应该使用set对象而不是list对象。还可以有一组集合。 - Alfredo Gimenez

@TonyBabarino 是的，这些列表包含了获胜的联盟；tobias_k - 正在研究这种方法；spiffman - 你不能将一个集合放入另一个集合（不可哈希化），你需要使用 frozenset。 - Jared Goguen

1

你可能也想避免生成非上升闭合集合，例如 [[1, 2], [1, 2, 3, 4]]（缺少 [[1, 2, 3]] 和 [[1, 2, 4]]）？ - David Eisenstat

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- tobias_k · Accepted Answer

这可能不是完整的解决方案，但它可能会指引你进一步探索。你可以将每个元素映射到一些关于“拓扑结构”的特征，以及它与其他元素的“连接”方式。你必须小心，不要考虑集合中的顺序，或者——显然——元素本身。例如，你可以考虑元素出现的频率、它出现在什么大小的组中等等。将这些指标组合成一个关键函数，按照该关键函数对元素进行排序，并按照该顺序为它们分配新名称。

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

这将您的两个示例列表映射到相同的“规范化”列表：

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