如何确定嵌套列表结构是否与另一个相同，但元素交换为新的

Question

假设我们有两个嵌套列表：L1 = [[0, 1], [0, 2]]和L2 = [[1, 2], [1, 3]]

问题是，一个列表中的整数和另一个列表中的整数之间是否存在一个双射，它将L1转换成L2？对于上面给出的L1和L2，答案是肯定的。你知道吗

双射：

• 旧的0变成新的1
• 旧的1变成新的2
• 旧的2变成新的3

回想一下我们的嵌套列表L1 = [[0, 1], [0, 2]]。如果我们应用上面描述的映射，那么我们得到L2 = [[1, 2], [1, 3]]，因此foo(L1, L2)应该返回True。foo是我们试图实现的相等运算符的名称。你知道吗

而且，秩序也不重要。每个列表都应视为一个数学“集合”

示例如下：

左列表：[[2, 1], [3, 1]]
右列表：[[1, 2], [1, 3]]：真 foo(left,right)返回True
为什么？
顺序不重要

左列表：[[2, 1], [3, 1]]
右列表：[[1, 2], [3, 4]]
foo(left,right)返回False
为什么？
左侧列表中的两个整数相同，但右侧列表中的所有整数彼此不同。你知道吗

left=[[2, 1], [3, 1]]
right=[[0, 1], [0, 1]]
foo(left, right)返回False
为什么？
右边的列表只包含2个不同的整数（0和1）。左边的列表包含3个不同的整数（1，2，3）

下面是一些较长的示例：

原始列表：[[0, 1], [0, 2], [1, 2], [1, 3], [0, 1, 2]]

A1:[[4, 1], [4, 0], [1, 0], [1, 3], [4, 1, 0]]：正确

A2:[[4, 1], [4, 0], [1, 3], [1, 0], [4, 0, 1]]：正确

B:[[1, 2], [3, 1], [2, 4], [1, 4], [2, 4, 1]]：正确

C:[[3, 2], [5, 2], [5, 0], [0, 2], [5, 0, 2]]：正确

D:[[5, 2], [5, 2], [3, 0], [0, 2], [5, 0, 2]]：错误

E:[[3, 0], [0, 3], [5, 0], [0, 2], [5, 0, 2]]：假

双射，例如A1：

ORIGINAL  A
 0        4
 1        1
 2        0
 3        3    

A2只是A1的重新排序

在示例B中，2和4与原始列表中的0和2扮演相同的角色。1和3在两个列表中的角色相同。你知道吗

在示例C中，0和5与原始列表中的0和2扮演相同的角色，2与原始列表中的1扮演相同的角色，3在两个列表中扮演相同的角色。 在示例D中，有两个相同的子列表（[5，2]），而原始列表没有重复的子列表。 在示例E中，所有四个length-2子列表中都有0，而在原始列表中，所有四个length-2子列表中都没有数字。你知道吗

下面是我尝试的代码，但是当一个小的数字（比如0）被交换为列表中最大的数字之一（比如说4）时，它就不起作用了。进行排序时，它无法识别4与0扮演的角色相同。因为低的数字可以换成高的数字，所以排序将不起作用。你知道吗

def CheckUnique(configs, newconfig):
    sortednewconfig = sorted([sorted(i) for i in newconfig])
    presentnumbers = []
    canonicalnewconfig = []
    for sub in sortednewconfig:
        for i in sub:
            if i not in presentnumbers:
                presentnumbers.append(i)
    for sub in sortednewconfig:
        cansub = []
        for i in sub:
            cansub.append(presentnumbers.index(i))
        canonicalnewconfig.append(cansub)
    if canonicalnewconfig not in configs:
        return True
    else:
        return False

Answer 1

您正在尝试求解一种被称为“graph isomorphism problem”的修改形式。现有的算法可以确定两个图是否同构，但是现有的算法都非常慢，特别是对于大型图。你知道吗

“图形”是带有点和线的图表。你知道吗

假设我们有两个嵌套列表：

L1 = [[0, 1], [0, 2], [1, 2], [1, 3], [0, 1, 2]]
L2 = [[4, 1], [4, 0], [1, 3], [1, 0], [4, 0, 1]] 

按照以下说明L1绘制图片：

• 对于子列表的每个元素，画一个点。例如，考虑子列表 [0, 1]。它将得到两个点，一个点代表0，一个点代表1。你知道吗
• 如果一组点在同一个位置，就在它们周围画一个圆 子列表。你知道吗
• 如果两个点代表同一个整数，在两个点之间画一条线。你知道吗

之后，将每组点（子列表）压缩为单个点。你知道吗

您可以为嵌套列表L2绘制一个类似的图，问题是，在删除所有数字之后，L1和L2的两个图看起来是否相同？你可能需要交换周围的颜色（蓝色边变成红色，红色变成蓝色，等等…），也可能需要移动点，直到它看起来一样。你知道吗

传统的图同构问题是将所有相同颜色的点连接起来的线。你的问题是稍微不同于传统的在你的边缘是彩色的。你知道吗

我认为，你可以摆脱单独的颜色和简单的数字，每个边缘的颜色数量，过去有。然后它变成一个“边加权图”

在google上搜索“边加权图的图同构”

你正在做的工作非常困难。我建议你在当地大学数学系的网站上寻找你可以联系的人。寻找职称为“图论者”的教授的电子邮件地址。联系他们，征求他们的意见。你知道吗

就像我说的，你的工作非常困难。你知道吗

我想你可以这样解决：

1. 为左侧列表构建边加权图
2. 为右列表构建边加权图
3. 确定这两个图是否同构。你知道吗