首页 > python > Python:从列表中获取n个可能的最小m值集

Python:从列表中获取n个可能的最小m值集 (Python: Get n possible minimum sets of m values from the list)

问题

给出了一个字典,它们的距离很少,其中键的名称和值 - 它的距离,即

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

问题是找到fe 6个最短路线以便从dict中获得3个不同的点,因此从给定的dict值中按顺序找到3个不同值的6个最低和。

我尝试按照以下方式执行此操作 - 将距离放入列表中,然后将其排序为:

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

然后只获得前6个组合,所以:

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

等等...

但正如你所看到的,它是不对的,因为4. 5+7+33 = 45而5. 7+15+18 = 40,所以应该在它之前,作为最低总和,所以“最短”的距离。我无法弄清楚任何算法和解决方案来处理这个问题。有什么提示可以做到吗?

谢谢。

解决方法

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

问题

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.

解决方法

Once you have the example_list = [5, 7, 15, 18, 22, 33], you can use this one liner to get the list of combination by 3 elements sorted by their sum:

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

Then pick the first six.

If you want also to keep track of the original keys:

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])]
相似信息