假设我们有两个嵌套列表: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
您正在尝试求解一种被称为“graph isomorphism problem”的修改形式。现有的算法可以确定两个图是否同构,但是现有的算法都非常慢,特别是对于大型图。你知道吗
“图形”是带有点和线的图表。你知道吗
假设我们有两个嵌套列表:
按照以下说明
L1
绘制图片:[0, 1]
。它将得到两个点,一个点代表0
,一个点代表1
。你知道吗之后,将每组点(子列表)压缩为单个点。你知道吗
您可以为嵌套列表
L2
绘制一个类似的图,问题是,在删除所有数字之后,L1和L2的两个图看起来是否相同?你可能需要交换周围的颜色(蓝色边变成红色,红色变成蓝色,等等…),也可能需要移动点,直到它看起来一样。你知道吗传统的图同构问题是将所有相同颜色的点连接起来的线。你的问题是稍微不同于传统的在你的边缘是彩色的。你知道吗
我认为,你可以摆脱单独的颜色和简单的数字,每个边缘的颜色数量,过去有。然后它变成一个“边加权图”
在google上搜索“边加权图的图同构”
你正在做的工作非常困难。我建议你在当地大学数学系的网站上寻找你可以联系的人。寻找职称为“图论者”的教授的电子邮件地址。联系他们,征求他们的意见。你知道吗
就像我说的,你的工作非常困难。你知道吗
我想你可以这样解决:
将
all
和any
与zip
一起使用:相关问题 更多 >
编程相关推荐