Подбор последовательности

Question

Есть необходимость подбора последовательности для получения меньшей суммы. К примеру есть набор abc и в нем возможно такие комбинации:

a-b-c = 2+6 = 8
a-c-b = 4+6 = 10
b-a-c = 3+4 = 7
b-c-a = 6+2 = 8
c-a-b = 2+2 = 4
c-b-a = 6+3 = 9

c-a-b = 2+2 = 4 - вот это наименьшая сумма, как написать код, что бы он выдавал такую последовательность?

table1 = [
['a-b', 2],
['a-c', 4],
['a-d', 6],
['b-a', 3],
['b-c', 6],
['b-d', 9],
['c-a', 2],
['c-b', 6],
['c-d', 8],
['d-a', 5],
['d-b', 7],
['d-c', 10],
]
seq = [a,b,c,]

Answer 1

Один из вариантов

import itertools

table1 = [
['a-b', 2],
['a-c', 4],
['a-d', 6],
['b-a', 3],
['b-c', 6],
['b-d', 9],
['c-a', 2],
['c-b', 6],
['c-d', 8],
['d-a', 5],
['d-b', 7],
['d-c', 10],
]
seq = ['a','b','c',]

# переделаем таблицу в словарь
d = { x[0]:x[1] for x in table1 }
# начальные значения суммы и комбинации
ts = sum(d.values())
tc = []
# перебираем все возможные перестановки
for x in itertools.permutations(seq,3) :
    # считаем текущую сумму и выбираем минимальную
    cs = sum(d[a+'-'+b] for a,b in zip(x[:-1], x[1:]))
    if cs < ts :
       ts = cs
       tc = x
print(tc)   # ('c', 'a', 'b')

БЛОГ НА HUSL

Подбор последовательности

Ответы (1 шт):