python - 比 python 中的嵌套循环更快的搜索方式

Question

我正在尝试为阵列找到最低预期成本的最佳顺序。

输入是:

input = [[390, 185, 624], [686, 351, 947], [276, 1023, 1024], [199, 148, 250]]

这是一个有四个选择的数组，第一个数字是成本，第二个数字是得到结果的概率，其中第一个 ([i][1]) 是分子，第二个 ([i][2]) 是分母。

目标是找到这些值/概率对的最佳顺序，以最少的总成本提供结果。

def answer(input):

    from itertools import permutations

    length = len(input)
    best_total = 999
    for combination in permutations(input):
        # print combination
        total = 0.0
        for i in range(0, length):
            current_value = 1.0
            for j in range(0, i):
                current_value = current_value * (1.0 -  \
                (float(combination[j][1]) / float(combination[j][2])))
            total = total + (float(combination[i][0]) * current_value)
            if total > best_total:
                i = length
        # print total
        if total <= best_total:
            best_total = total
            best_combination = combination

    answer = map(input.index, best_combination)

    return answer

运行:

print answer(input)

应该返回

[2, 3, 0, 1]

对于给定的输入。

这显然是一个详尽的搜索，如果有四个以上的选择，它会很快变得非常慢。我考虑过二叉搜索树，因为它们的输入非常相似，但我不知道如何实现它。

我已经为此工作了四天，似乎无法想出适用于任何输入的快速版本(假设成本和概率为正)。

这不是作业之类的，只是我一直想弄清楚的一个谜题。

Answer 1

我会确定原始数组中每个案例的值，存储这些值，然后对列表进行排序。这是在 python 3 中，所以我不知道这是否会影响您。

确定原始数组中每个案例的值并存储它们:

inputA = [[390, 185, 624], [686, 351, 947], [276, 1023, 1024], [199, 148, 250]]
results = []
for idx,val in enumerate(inputA):
    results.append((val[0]*val[1]/val[2], idx))

排序列表，提取位置:

l = lambda t:t[1]
print(list(map(l,sorted(results,reverse=True))))

遍历列表是O(n)，排序是O(nlogn)。 Map/list/print 再次迭代 O(n) 因此性能应该是 O(nlogn)。