algorithm - 如何有效地搜索排列

Question

我正在尝试搜索列表列表的排列，对每个排列进行评分，并找到最小值。当列表列表的长度为四时，我可以通过对解决方案进行硬编码来实现。我的问题是如何将我的解决方案推广到 50 以内的任意长度？如何避免编写一系列 for 循环？

answer = {}
l=[[16,5,6],[6,3,4],[5,1,2],[10,1,4]]
lowest = get_expected_value(l)
for x in l:
    for y in l:
        for z in l:
            for a in l:
                if x != y and x != z and x != a and y != z and y != a and z != a:
                     if get_expected_value([x,y,z,a]) <= lowest:
                         answer[get_expected_value([x,y,z,a])] = [x,y,z,a]
                         lowest = get_expected_value([x,y,z,a])

print ans[min(ans.keys())]

get_expected_value定义如下:

 def get_expected_value(list_minions):
        expected = 0
        for item in xrange(len(list_minions)):
            if item == 0:
                expected += list_minions[0][0]
            else:
                expected += (list_minions[item][0])*(1.0 - (list_minions[item-1][1]/float(list_minions[item-1][2])))
        return expected

Answer 1

这是处理任意长度列表 l 的解决方案(并不像@mhum 指出的那样，它总是会在任何合理的时间内完成)使用相同的 get_expected_value 函数。

from itertools import permutations
l = ((16,5,6),(6,3,4),(5,1,2),(10,1,4)) # in general, you should choose a different letter than `l` for variable names, as it can be confused with `1`
print min(permutations(l), key=get_expected_value)

关键思想是利用 itertools 的 permutation 生成器函数来完成获取列表 l 的所有排列的肮脏工作。最后，您可以使用 min 的 key 关键字参数来指定您想要的，而不是自己跟踪最小值给定对象集合的最小值(在本例中，对象是 l 的排列)，其中它们的“值”由与 key 关联的函数，在本例中为 get_expected_value。所以我们有: