Python：从列表中获取n个可能的最小m值集合

Question

给定一个字典，其中包含几个点及其距离，其中键 - 点的名称，值 - 它的距离，即

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

问题是找到f.e。 6 最短路线为了 3 与 dict 不同的点，所以 6 的最小总和 3 与给定字典值的不同值按顺序排列。

我尝试通过以下方式做到这一点 - 将距离放入列表中，然后将其排序为：

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

然后只得到前 6 个组合，所以：

5+7+15

5+7+18

5+7+22

5+7+33

7+15+18

等等...

但是如你所见，这是不对的，因为 4.5+7+33 = 45 而 5.7+15+18 = 40，所以它应该在它之前，作为最低总和，所以 "shortest" 距离。我想不出任何算法和解决方案来处理这个问题。有什么技巧可以做到吗？

谢谢。

Answer 1

您可以使用 powerset recipes from itertools, combine it with collection.defaultdict 并且仅使用具有 3 个元素的元组。这会产生过多的数据 - 如果你有 huge 字典，这不是最佳选择：

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

Answer 2

一旦你有了 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 3

您可以使用 itertools 的幂集收据，将其与 colleciton.defaultdict 结合使用，并仅使用具有 3 个元素元组的那些：

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

Python：从列表中获取n个可能的最小m值集合

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

python

list

combinatorics