Putting a list in the same order as another list

Question

There's a bunch of questions that are phrased similarly, but I was unable to find one that actually mapped to my intended semantics.

There are two lists, A and B, and I want to rearrange B so that it is in the same relative order as A - the maximum element of B is in the same position as the current position of the maximum element of A, and the same for the minimum element, and so on.

Note that A is not sorted, nor do I want it to be.

As an example, if the following were input:

a = [7, 14, 0, 9, 19, 9]
b = [45, 42, 0, 1, -1, 0]

I want the output to be [0, 42, -1, 0, 45, 1].

Please note that the intended output is not [0, 45, 1, 0, 42, -1], which is what it would be it you zipped the two and sorted by A and took the resulting elements of B (this is what all of the other questions I looked at wanted).

Here's my code:

def get_swaps(x):
    out = []

    if len(x) <= 1:
        return out

    y = x[:]
    n = -1

    while len(y) != 1:
        pos = y.index(max(y))
        y[pos] = y[-1]
        y.pop()
        out.append((pos, n))
        n -= 1

    return out

def apply_swaps_in_reverse(x, swaps):
    out = x[:]
    for swap in swaps[::-1]:
        orig, new = swap
        out[orig], out[new] = out[new], out[orig]
    return out

def reorder(a, b):
    return apply_swaps_in_reverse(sorted(b), get_swaps(a))

The approach is basically to construct a list of the swaps necessary to sort A via selection sort, sort B, and then apply those swaps in reverse. This works, but is pretty slow (and is fairly confusing, as well). Is there a better approach to this?

Answer 1

a = [7, 14, 0, 9, 19, 9]
b = [45, 42, 0, 1, -1, 0]
print zip(*sorted(zip(sorted(b), sorted(enumerate(a), key=lambda x:x[1])), key=lambda x: x[1][0]))[0]
#or, for 3.x:
print(list(zip(*sorted(zip(sorted(b), sorted(enumerate(a), key=lambda x:x[1])), key=lambda x: x[1][0])))[0])

result:

(0, 42, -1, 0, 45, 1)

You sort a, using enumerate to keep track of each item's original index. You zip the result with sorted(b), then re-sort the whole thing based on a's original indices. Then you call zip once more to extract just b's values.