A faster way to search than nested loops in python
I am trying to find the optimal least expected cost order for an array.
Entrance:
input = [[390, 185, 624], [686, 351, 947], [276, 1023, 1024], [199, 148, 250]]
This is an array of four options, the first number is the cost, and the second is the probability of getting a result, the first ( [i][1]
) of which is the numerator and the second ( [i][2]
) is the denominator.
The goal is to find the optimal ordering of these value / probability pairs that will produce a result of at least total cost.
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
Duration:
print answer(input)
should return
[2, 3, 0, 1]
for the given input.
This is obviously an exhaustive search that changes very quickly very quickly with more than four options. I have looked at binary search trees as the input for them is very similar, however I cannot figure out how to implement it.
I've been working on this for four days and don't seem to come up with a quick version that works for any input (assuming positive costs and probabilities).
This is not homework or anything, just a puzzle I was trying to figure out.
source to share
I would determine the value of each case in the original array, store those values, and then sort the list. It's in python 3, so I don't know if this affects you.
Determining the meaning of each case in the original array and storing it:
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))
Sorting the list, extracting positions:
l = lambda t:t[1]
print(list(map(l,sorted(results,reverse=True))))
Iterating over the list O(n)
and sorting is O(nlogn)
. Map / list / print repeats it again for O(n)
, so performance should be O(nlogn)
.
source to share