Sort 2 lists in Python based on the ratio of individual matching items or based on a third list

Question

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

For this, I have 2 arrays:

• Values
• Weight

The value of the elements [n] corresponds to the weight of the elements [n]. Thus, we can compute value_per_unit as:

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

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

for example: If

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

Then

• values_per_unit = [3.0, 2.0, 4.0]

• and therefore the per_unit_sorted values ​​will be [2.0, 3.0, 4.0]

I need arrays of values ​​and weights 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 extremely inefficient to me 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, write down the lists to put them together.

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

Then sort by partial value by 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 relation as the first element.

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

The first seems to be slightly faster in some quick tests. If you are looking for the best algorithm, you may have to unwrap things and the solution will not be so concise.

And to answer a comment from @TomWyllie, if you already have a list of odds, you can use:

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

Note that these last two solutions differ from the original solution in the case when two pairs are equally related. These solutions will be sorted a second time by value, while the first solution will contain items in the same order as the original list.

Answer 2

For a more explicit (but possibly less pythonic) solution, create a list of indexes sorted by value in that index in value_per_unit , and change the order of values and weights accordingly.

 sorted_indices = [index for index, value in sorted(enumerate(value_per_unit), key=lambda x: x[1])] values = [values[i] for i in sorted_indices] weights = [weights[i] for i in sorted_indices] print(values, weights) 

Outputs:

 ([100, 60, 120], [50, 20, 30]) 

You can remove this by eliminating unnecessary extra loops using zip , and with a generator expression;

 values, weights = zip(*((values[i], weights[i]) for i, value in sorted(enumerate(value_per_unit), key=lambda x: x[1]))) print(values) print(weights) 

What are the exits;

 (100, 60, 120) (50, 20, 30) 

Note that these final values ​​are tuples not lists . If you really need the output to be a list, simple values, weights = map(list, (values, weights)) enough. You could even wrap this in a single liner, although by now it is probably quite difficult to keep track of what is happening.

Answer 3

An elegant way to do this is to make a multidimensional list with values ​​and weights:

 for i in range(len(values)): values_and_weights.append([values[i], weights[i]) # The resulting list is [[60, 20], [100, 50], [120, 30]] 

Then use the sort method with the value divided by weight as the key.

 values_and_weights.sort(key=(lambda x: x[0]/x[1])) 

Answer 4

The problem you are facing is with the calculation of the field above each element (the element i will have the calculated values[I]/weights[I] ). To solve this problem and still be very easy to understand, you can turn it into a tuple of this form: ( calculated_value, (value, weight) ) , for each element.

This approach makes it easy to read and understand. Take a look at the following solution:

 values = [60, 100, 120] weights = [20, 50, 30] value_per_unit = [] for I in range(len(values)): value_per_unit.append( (values[I]/weights[I], (values[I], weights[I])) ) sorted_value_per_unit = sorted(value_per_unit, key=lambda x: x[0]) sorted_values = [] sorted_weights = [] for I in range(len(values)): (value, weight) = sorted_value_per_unit[I][1] sorted_values.append(value) sorted_weights.append(weight) print(str(sorted_values)) print(str(sorted_weights)) 

Also note that I changed the loop from the source code:

range(values) changed to range(len(values))

Since the range will require the length of the list, not the list itself.