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

i want calculate difference between 2 values in distancetable read in file, csv file number of cities distances between them. in .csv-file have first row cities, this:

barcelona;belgrade;berlin

the next rows distances between cities, written this:

0;1528.13;1497.61

1528.13;0;999.25

1497.61;999.25;0

for example, distance barcelona barcelona 0, (first number), barcelona , belgrade 1528.13, (second), belgrade , berlin 999.25.. etc

i trying create algorithm search shortest path through cities in file this. need use python , permutations itertools.

i don't know how can use permutations correctly can add distance different possibilites. how can this?

so importing permutations, csv, reading in file, , and starting here...

from itertools import permutations import csv  # read data file distance_table = [] open('european_cities.csv') file:   reader = csv.reader(file,delimiter=';')   # first row city names   city_names = reader.next()   # rest of rows distance table   row in reader:     distance_table.append([float(cell) cell in row]) 

so can fore example see distance_table distance between city , city b this:

distance_table[city_a][city_b]

how can loop through combinations in permutation when want each city appear once??

i want example: citya-cityb + cityb-cityc + cityc-citya , not: citya-cityb + citya-cityc + cityb-cityc + cityc-citya etcetra . . .

i use different algorithms here, firstly stupid algorithm lie brute force see difference in time between , smarter algorithm, shortest-path algorithm.

but don't know how can loop through cities. how?

you want permutations without city appearing twice, yet example has starting city (citya) listed again @ end:

i want example: citya-cityb + cityb-cityc + cityc-citya

so, assuming first city appearing again @ end meant, think following shows how generate permutations of cities want — if assumption wrong, remove 1 line first city duplicated.

in order differing total distances (with 3 it's same), added fourth city , changed output format it's more compact better accommodate more cities.

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 

here's code:

from __future__ import print_function import csv import functools try:     itertools import izip, imap except importerror:  # python 3     izip = zip     imap = map itertools import permutations, repeat  # create dictance dictionary csv data file entries this: #     (city_a, city_b): float(distance-between-city_a-and-city_b) # pairs of city names in file. data_filename = 'european_cities.csv' dist_dict = {} open(data_filename, 'r') file:     reader = csv.reader(file, delimiter=';')     cities = next(reader)  # header row     num_cities = len(cities)     city in cities:  # should row of distances each city         from_city_iter = repeat(city, num_cities)         dist_dict.update((pair 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 1 iteration     return izip(a, b)  tour in permutations(cities, len(cities)):     tour += (tour[0],)  # make round trip appending starting city     route = '->'.join(tour)     dist = sum(dist_dict[city_a, city_b] city_a, city_b in pairwise(tour))     print('{:^49}: {:,}'.format(route, dist)) 

output:

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