混洗列表时的不同结果

Question

我想将未完成的图分成单独的，不相关的物体。图表的边缘在列表edges中。

该代码在洗牌边缘顺序时给出了不同的结果。这是为什么？

from random import shuffle 

edges = [('7', '9'), ('2', '8'), ('4', '10'), ('5', '9'), ('1', '2'), ('1', '6'), ('6', '10')] 
bodylist = [] 
shuffle(edges) 

for edge in edges: 
    #If at least one node of the edge is anywhere in bodylist, append the new nodes to that list. 
    try: 
     index = [i for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body][0] 
     bodylist[index].append(edge[0]) 
     bodylist[index].append(edge[1]) 
    #If not, make a new list containing the new nodes. 
    except: 
     bodylist.append([edge[0], edge[1]]) 

print([set(x) for x in bodylist]) 

预期输出：[{'1', '2', '8', '4', '6', '10'}, {'9', '5', '7'}]

一些实际产出：[{'9', '5', '7'}, {'1', '2', '8'}, {'10', '4', '6', '1'}]

[{'9', '7', '5'}, {'6', '2', '1', '8'}, {'6', '10', '4'}]

注意，预计产量也出来不时。 （它应该总是如此）

我也会喜欢不同的方法，因为这个可能不是最好的。

Answer 1

假设你有三条边[(1, 2), (3, 4), (2, 3)]。 这描述了一个连通图。

但是，您的代码将首先检查(1, 2)，找不到任何内容，因此请将其添加到bodylist。

然后，它会查找(3, 4)，找不到3或4因此将其添加为新列表。

最后它会将(2, 3)添加到第一个列表中，但它不会回来修复它的错误，它不会意识到(3, 4)属于同一个主体。

为了解决这个问题，你可以循环完全通过剩余的边缘每次你为了添加一个新的边缘于一体的，以检查是否存在连接：

while edges: 
    current_edge = edges.pop(0) 
    body = {current_edge[0], current_edge[1]} 
    i = 0 
    while i < len(edges): 
     if edges[i][0] in body or edges[i][1] in body: 
      body.add(edges[i][0]) 
      body.add(edges[i][1]) 
      edges.pop(i) # Edge added, no need to check it again 
      i = 0 # Restart the loop 
     else: 
      i += 1 
    bodylist.append(body) 

什么你正在寻找被称为图的connected component。

如果您正在寻找高效的算法，您应该看看this answer。

Answer 2

这是因为你的算法错了。你的算法的问题是它取决于我们开始创建body列表的边缘。为了解释这个问题，我们举一个简单的例子，用4条边作为 - edges = [('1','2'),('2','3'),('3','4'),('1','4')]。

第一种情况 -

>>> edges = [('1','2'),('2','3'),('3','4'),('1','4')] 
>>> bodylist = [] 
>>> for edge in edges: 
...  #If at least one node of the edge is anywhere in bodylist, append the new nodes to that list. 
...  try: 
...   index = [i for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body][0] 
...   bodylist[index].append(edge[0]) 
...   bodylist[index].append(edge[1]) 
...  #If not, make a new list containing the new nodes. 
...  except: 
...   bodylist.append([edge[0], edge[1]]) 
... 
>>> print([set(x) for x in bodylist]) 
[{'4', '1', '3', '2'}] 

你得到一个单一的机构，其中顶点 - 1, 2, 3, 4。为什么？

因为你开始于（1,2）将其添加到身体列表。然后你拿了（2,3），你看到2已经存在于正文列表中添加的项目中，你再次将它添加到同一个项目中，并且继续，所有项目都添加到同一个主体中。

---

现在，让我们以不同的顺序采取相同的边缘 - edges = [('1','2'),('3','4'),('2','3'),('1','4')]。这原来是 -

>>> edges = [('1','2'),('3','4'),('2','3'),('1','4')] 
>>> bodylist = [] 
>>> .... #same logic 
>>> print([set(x) for x in bodylist]) 
[{'4', '1', '3', '2'}, {'4', '3'}] 

正如你所看到的这个时候，你有两个不同的机构（显然他们错了），为什么？

你又开始使用（1,2），把它作为一个身体添加到bodylist中，然后你拿（3,4），检查它，你会发现任何物体都没有任何顶点，因此你将它添加到一个单独的主体中。拿第三个元素（2,3）来说，你会发现第一个元素和第二个元素都存在，但是你的逻辑是只取第一个元素并将元素添加到该元素中。 （你看到你要去哪里错了？）

---

这就是为什么你会得到不同的结果，当你洗牌的名单，因为订单是你的逻辑很重要（这是错误的）。

您需要做的是，如果您在多个实体中找到边的顶点，则需要将两个实体合并到一个实体中。

---

另一种意见，我们不需要列表添加到bodylist相反，我们可以使用sets每个body。

样品溶液会是什么样子 -

from random import shuffle 

edges = [('7', '9'), ('2', '8'), ('4', '10'), ('5', '9'), ('1', '2'), ('1', '6'), ('6', '10')] 
bodylist = [] 
shuffle(edges) 

for edge in edges: 
    bodies = [body for i, body in enumerate(bodylist) if edge[0] in body or edge[1] in body] 
    if len(bodies) > 0: 
     tempset = {edge[0],edge[1]} 
     for x in bodies: 
      tempset.update(x) 
      print('tempset :',tempset) 
      bodylist.remove(x) 
     bodylist.append(tempset) 
    else: 
     bodylist.append({edge[0],edge[1]}) 

print([set(x) for x in bodylist])