Python: получить n возможных минимальных наборов значений m из списка

Question

Дан словарь с несколькими точками с их расстоянием, где ключ - название точки, а значение - это расстояние, т. Е.

points_dict = {"a": 18, "b": 7, "c": 15, "d": 22, "e": 33, "f": 5}

Вопрос в том, чтобы найти е.е. 6 кратчайших маршрутов для 3 различных точек от dict, поэтому 6 наименьших сумм 3 различных значений от заданных значений dict в заказ.

Я попытался сделать это следующим образом - получить расстояния в списке, а затем отсортировать его по адресу:

example_list = [5, 7, 15, 18, 22, 33]

А затем просто получите первые 6 комбинаций, так:

1. 5 + 7 + 15 * * тысяча двадцать один
2. 5 + 7 + 18
3. 5 + 7 + 22 * ​​1025 *
4. 5 + 7 + 33

и так далее ...

Но, как вы видите, это не правильно, потому что 4. 5+7+33 = 45 при 5. 7+15+18 = 40, поэтому должно быть перед ним, как наименьшая сумма, так что «кратчайшее» расстояние. Я не могу понять какой-либо алгоритм и решение, чтобы справиться с этим. Любые советы, как это можно сделать?

Спасибо.

Answer 1

Получив example_list = [5, 7, 15, 18, 22, 33], вы можете использовать этот вкладыш, чтобы получить список комбинации по 3 элементам, отсортированным по их сумме:

from itertools import combinations

sorted(list(combinations(example_list, 3)),key=sum)

#=> [(5, 7, 15), (5, 7, 18), (5, 7, 22), (5, 15, 18), (7, 15, 18), (5, 15, 22), (7, 15, 22), (5, 7, 33), (5, 18, 22), (7, 18, 22), (5, 15, 33), (7, 15, 33), (15, 18, 22), (5, 18, 33), (7, 18, 33), (5, 22, 33), (7, 22, 33), (15, 18, 33), (15, 22, 33), (18, 22, 33)]

Затем выберите первые шесть.

Если вы хотите также отслеживать исходные ключи:

tmp_list = [[k, v] for k, v in points_dict.items()]
sorted(list(combinations(tmp_list, 3)), key = lambda x: sum(i[1] for i in x) )[0:6]

#=> [(['c', 15], ['b', 7], ['f', 5]), (['a', 18], ['b', 7], ['f', 5]), (['b', 7], ['d', 22], ['f', 5]), (['a', 18], ['c', 15], ['f', 5]), (['a', 18], ['c', 15], ['b', 7]), (['c', 15], ['d', 22], ['f', 5])]

Answer 2

Вы можете использовать квитанцию ​​powerset от itertools, объединить ее с colleciton.defaultdict и использовать только те, у которых есть три элемента:

from itertools import combinations, chain

# https://docs.python.org/2/library/itertools.html#recipes
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


points_dict = {"a": 18, "b": 7, "c": 15, "d": 22, "e": 33, "f": 5}
from collections import defaultdict
d = defaultdict(list)
for s in powerset(points_dict.values()):
    if len(s) == 3:
        d[sum(s)].append(s) 

sor = sorted(d)
for s in sor:
    print(s, d[s])

Выход:

27 [(7, 15, 5)]
30 [(18, 7, 5)]
34 [(7, 22, 5)]
38 [(18, 15, 5)]
40 [(18, 7, 15)]
42 [(15, 22, 5)]
44 [(7, 15, 22)]
45 [(18, 22, 5), (7, 33, 5)]
47 [(18, 7, 22)]
53 [(15, 33, 5)]
55 [(18, 15, 22), (7, 15, 33)]
56 [(18, 33, 5)]
58 [(18, 7, 33)]
60 [(22, 33, 5)]
62 [(7, 22, 33)]
66 [(18, 15, 33)]
70 [(15, 22, 33)]
73 [(18, 22, 33)]

Answer 3

Вы можете использовать рецепты powerset от itertools, объединить их с collection.defaultdict и использовать только те, которые имеют наборы из 3 элементов. Это приведет к перепроизводству данных - не оптимально, если у вас есть огромные словари:

from itertools import combinations, chain
from collections import defaultdict

# https://docs.python.org/3/library/itertools.html#recipes
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)

    # you can hardcode your 3-tuples here as well and eliminate lots of data and filtering
    # return combinations(s, 3)

    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


points_dict = {"a": 18, "b": 7, "c": 15, "d": 22, "e": 33, "f": 5}

d = defaultdict(list)
for s in powerset(points_dict.values()):
    if len(s) == 3:
        d[sum(s)].append(s) 

sor = sorted(d)
for s in sor:
    print(s, d[s])

Выход:

27 [(7, 15, 5)]
30 [(18, 7, 5)]
34 [(7, 22, 5)]
38 [(18, 15, 5)]
40 [(18, 7, 15)]
42 [(15, 22, 5)]
44 [(7, 15, 22)]
45 [(18, 22, 5), (7, 33, 5)]
47 [(18, 7, 22)]
53 [(15, 33, 5)]
55 [(18, 15, 22), (7, 15, 33)]
56 [(18, 33, 5)]
58 [(18, 7, 33)]
60 [(22, 33, 5)]
62 [(7, 22, 33)]
66 [(18, 15, 33)]
70 [(15, 22, 33)]
73 [(18, 22, 33)]