我想用排列计算 "distance_table = []" 中两个值之间的差值，在这种情况下如何正确使用排列？

Question

我想计算从文件中读入的距离表中两个值之间的差异，该文件是一个 csv 文件，其中包含许多城市以及它们之间的距离。在 .csv 文件中，第一行是城市，像这样：

Barcelona;Belgrade;Berlin

下一行是城市之间的距离，写成这样：

0;1528.13;1497.61

1528.13;0;999.25

1497.61;999.25;0

例如巴塞罗那到巴塞罗那的距离是0，（第一个数字），巴塞罗那和贝尔格莱德是1528.13，（第二个），贝尔格莱德和柏林999.25..等

我正在尝试创建一种算法来搜索通过文件中所有城市的最短路径，就像这样。但我将需要使用 Python 并且可能需要使用 itertools 的排列。

我不知道如何正确使用排列，以便将不同可能性的距离加在一起。我该怎么做？

所以我正在导入排列、csv、读取文件，然后从这里开始...

from itertools import permutations
import csv

# Read data file
distance_table = []
with open('european_cities.csv') as file:
  reader = csv.reader(file,delimiter=';')
  # First row is the city names
  city_names = reader.next()
  # The rest of the rows are the distance table
  for row in reader:
    distance_table.append([float(cell) for cell in row])

所以现在我可以例如从 distance_table 中看到城市 A 和城市 B 之间的距离，如下所示：

distance_table[city_A][city_B]

当我只希望每个城市出现一次时，如何遍历排列中的所有组合？？

我想要例如：cityA-cityB + cityB-cityC + cityC-cityA 而不是：cityA-cityB + cityA-cityC + cityB-cityC + cityC-cityA 等等。 . .

我想在这里使用不同的算法，首先是一个愚蠢的算法，用蛮力来查看它与更聪明的算法（如最短路径算法）之间的时间差异。

但我不知道如何在城市中循环。怎么样？

Answer 1

如果你稍微考虑一下，你会发现 cityA-cityB + cityB-cityC + cityC-cityA 形式的组合实际上只是 A,B,C 稍作修改。你能想出一种算法将 A,B,C 转换为 cityA-cityB + cityB-cityC + cityC-cityA 吗？也许您可以将这种修改功能与 python 工具结合起来，从您的列表中生成独特的组合。

Answer 2

使用排列函数的一种简单方法是：

N = len(city_names)
for perm in permutations(range(N)):
  dist = sum(distance_table[perm[i]][perm[(i+1)%N]] for i in range(N))
  print perm,dist

Answer 3

您说您希望所有没有任何城市的排列出现两次，但您的示例在末尾再次列出了起始城市 (cityA)：

I want for example: cityA-cityB + cityB-cityC + cityC-cityA

因此，假设最后再次出现的第一个城市实际上就是您的意思，我认为下面显示了如何生成您想要的城市排列 — 如果该假设错误，只需删除其中的一行第一个城市重复了。

为了获得不同的总距离（三个始终相同），我添加了第四个城市并更改了输出格式，使其更紧凑以更好地容纳更多城市。

Barcelona;Belgrade;Berlin;Brussels
0;1528.13;1497.61;1346.0
1528.13;0;999.25;1723.0
1497.61;999.25;0;764.0
1346.0;1723.0;764.0;0

代码如下：

from __future__ import print_function
import csv
import functools
try:
    from itertools import izip, imap
except ImportError:  # Python 3
    izip = zip
    imap = map
from itertools import permutations, repeat

# Create a dictance dictionary from csv data file with entries like this:
#     (city_a, city_b): float(distance-between-city_a-and-city_b)
# for all pairs of city names in the file.
data_filename = 'european_cities.csv'
dist_dict = {}
with open(data_filename, 'r') as file:
    reader = csv.reader(file, delimiter=';')
    cities = next(reader)  # header row
    num_cities = len(cities)
    for city in cities:  # should be a row of distances for each city
        from_city_iter = repeat(city, num_cities)
        dist_dict.update((pair for pair in izip(izip(from_city_iter, cities),
                                                imap(float, next(reader)))
                            if pair[1])) # skip 0 distances (city_a == city_b)

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2,s3), ..."
    a, b = iter(iterable), iter(iterable)
    next(b)  # advance second iterator one iteration
    return izip(a, b)

for tour in permutations(cities, len(cities)):
    tour += (tour[0],)  # make round trip by appending starting city
    route = '->'.join(tour)
    dist = sum(dist_dict[city_a, city_b] for city_a, city_b in pairwise(tour))
    print('{:^49}: {:,}'.format(route, dist))

输出：

Barcelona->Belgrade->Berlin->Brussels->Barcelona : 4,637.38
Barcelona->Belgrade->Brussels->Berlin->Barcelona : 5,512.74
Barcelona->Berlin->Belgrade->Brussels->Barcelona : 5,565.86
Barcelona->Berlin->Brussels->Belgrade->Barcelona : 5,512.74
Barcelona->Brussels->Belgrade->Berlin->Barcelona : 5,565.86
Barcelona->Brussels->Berlin->Belgrade->Barcelona : 4,637.38
 Belgrade->Barcelona->Berlin->Brussels->Belgrade : 5,512.74
 Belgrade->Barcelona->Brussels->Berlin->Belgrade : 4,637.38
 Belgrade->Berlin->Barcelona->Brussels->Belgrade : 5,565.86
 Belgrade->Berlin->Brussels->Barcelona->Belgrade : 4,637.38
 Belgrade->Brussels->Barcelona->Berlin->Belgrade : 5,565.86
 Belgrade->Brussels->Berlin->Barcelona->Belgrade : 5,512.74
  Berlin->Barcelona->Belgrade->Brussels->Berlin  : 5,512.74
  Berlin->Barcelona->Brussels->Belgrade->Berlin  : 5,565.86
  Berlin->Belgrade->Barcelona->Brussels->Berlin  : 4,637.38
  Berlin->Belgrade->Brussels->Barcelona->Berlin  : 5,565.86
  Berlin->Brussels->Barcelona->Belgrade->Berlin  : 4,637.38
  Berlin->Brussels->Belgrade->Barcelona->Berlin  : 5,512.74
 Brussels->Barcelona->Belgrade->Berlin->Brussels : 4,637.38
 Brussels->Barcelona->Berlin->Belgrade->Brussels : 5,565.86
 Brussels->Belgrade->Barcelona->Berlin->Brussels : 5,512.74
 Brussels->Belgrade->Berlin->Barcelona->Brussels : 5,565.86
 Brussels->Berlin->Barcelona->Belgrade->Brussels : 5,512.74
 Brussels->Berlin->Belgrade->Barcelona->Brussels : 4,637.38

Answer 4

这个解决方案怎么样：

from itertools import permutations
import csv

    sums = []

    for p in permutations(distance_table[0], 2):
      sums.append(sum(p))

    for s in sums:
        print(s)

我想用排列计算 "distance_table = []" 中两个值之间的差值，在这种情况下如何正确使用排列？

I want to calculate the difference between two values in a "distance_table = []" with permutations, how can I use permutations correctly in this case?

python

csv

algorithm

combinations

permutation