Python: Get n possible minimum sets of m values from the list

2825 views python
0

There is given a dictionary with few points with their distance where key - name of the point, and value - it's distance, i.e.

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

The question is to find f.e. 6 shortest routes in order for 3 different points from the dict, so 6 lowest sums of 3 different values from given dict values in order.

I tried to do this in following way - get distances into a list, then sort it to:

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

And then just get first 6 combinations, so:

  1. 5+7+15
  2. 5+7+18
  3. 5+7+22
  4. 5+7+33
  5. 7+15+18

and so on...

But as you can see, it isn't right, because 4. 5+7+33 = 45 while 5. 7+15+18 = 40, so it should be before it, as lowest sum, so "shortest" distance. I can't figure out any algorithm and solution to deal with this. Any tips how it can be done?

Thank you.

answered question

Do you start at a certain point? It looks to me this is a variant of the subset sum problem, where you can then "harvest" combinations at the end that are minimal. Or you could use a variant of Dijkstra's algorithm to generate minimal combinations after 3 "hops".

1 Answer

6

You can use the powerset recipes from itertools, combine it with collection.defaultdict and use only those with 3 element tuples. This will overproduce data though - its not optimal if you have huge dictionaries:

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])

Output:

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)]

posted this

Have an answer?

JD

Please login first before posting an answer.