Sort 2 lists in Python based on the ratio of individual corresponding elements or based on a third list

Question

I am trying to write different implementations for a fractional knapsack problem.

For this I have 2 arrays:

1. Values
2. Weights

The elements value[n] corresponds to element weights[n]. So we can calculate value_per_unit as:

for I in range(values):
    value_per_unit.append(values[I]/weights[I])
value_per_unit.sort()

I now need the 2 arrays (values and weights) to be sorted according to the value_per_unit array

eg: If

• values = [60, 100, 120]
• weights = [20, 50, 30]

Then

• values_per_unit = [3.0, 2.0, 4.0]

• and so values_per_unit_sorted will be [2.0, 3.0, 4.0]

I need the values and weights arrays to become:

• values_sorted = [100,60,120]
• weights_sorted = [50,20,30]

Is there a way to achieve this using simple lambda functions?

I can still do something like this, but it seems highly inefficient every-time I need to access the elements:

weights[(value_per_unit_sorted.index(max(value_per_unit_sorted)))]

Answer 1

In one line:

values, weights = zip(*sorted(zip(values, weights), key=lambda t: t[0]/t[1]))

---

To explain: First, zip the lists to pair them.

pairs = zip(values, weights) 
# [(60, 20), (100, 50), (120, 30)]

Then, sort by the quotient of value to weight.

sorted_pairs = sorted(pairs, key=lambda t: t[0]/t[1]) 
# [(100, 50), (60, 20), (120, 30)]

Finally, unzip them back into separate lists.

values, weights = zip(*sorted_pairs)
# (100, 60, 120), (50, 20, 30)

---

An alternative is to construct tuples explicitly containing the ratio as the first element.

ratios, values, weights = zip(*sorted((v/w, v, w) for v, w in zip(values, weights)))

The former appears to be slightly faster in some quick testing. If you're looking for an optimal algorithm, you're probably going to have to unroll things and the solution will not be as concise.

And to address the comment from @TomWyllie, if you already have the list of ratios, you can use:

ratios, values, weights = zip(*sorted(zip(ratios, values, weights)))

Note that these last two solutions differ from the initial solution in the case where two pairs have an equal ratio. These solutions will sort secondarily by value, while the first solution will keep the items in the same order as the original list.