How to generate an optimal order of multiple elements based on pairwise element score values

Question

I have a number of elements, let say [a, b, c, d], and for each pairwise combination I have a score:

[['d-a', 0], ['a-b', 0], ['b-a', 0],
 ['a-c', 2], ['c-a', 0], ['a-d', 2],
 ['d-b', 1], ['b-c', 2], ['c-b', 0],
 ['b-d', 2], ['d-c', 2], ['c-d', 2]]

I am looking for a way in Python to put these elements in successive order in a way that will minimize the sum of these scores. Each unit must occur once and only once. Notice that the succession of two elements is also of importance, i.e. 'd-a' = 0 while 'a-d' = 2.

I'll be very grateful for your answers.

Thank you

Simon

Answer 1

elements = ['a', 'b', 'c', 'd']
scores = [['d-a', 0], ['a-b', 0], ['b-a', 0], ['a-c', 2], ['c-a', 0], ['a-d', 2],
          ['d-b', 1], ['b-c', 2], ['c-b', 0], ['b-d', 2], ['d-c', 2], ['c-d', 2]]

s = dict(scores)
print(min(itertools.permutations(elements),
          key=lambda p: sum(s[a+'-'+b] for a, b in zip(p, p[1:]))))

Prints ('c', 'a', 'b', 'd').