Qfyilyi

Given two lists, for example:

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

b = [2, 4, 6, 7, 0, 1, 3, 5, 8, 9]

I wish to find a series of moves which will transform list a into list b, where each move is an operation:

move(from_index, to_index)

which moves the element at location from_index and places it at location to_index. So if:

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

then the operation move(3,1) on the list a will transform a into:

a = [0, 3, 1, 2, 4, 5, 6, 7, 8, 9]

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

b = [2, 4, 6, 7, 0, 1, 3, 5, 8, 9]

move(0, 8)

a = [1, 2, 3, 4, 5, 6, 7, 0, 8, 9]

move(0, 8)

a = [2, 3, 4, 5, 6, 7, 0, 1, 8, 9]

move(1, 8)

a = [2, 4, 5, 6, 7, 0, 1, 3, 8, 9]

move(2, 8)

a = [2, 4, 6, 7, 0, 1, 3, 5, 8, 9]

a==b

Hopefully that's what you're looking for.

Basically, start with the left- most element and move it to where it should be. For example, I took 0 and placed it right after the value that it is supposed to eventually end up behind, which is 7. I continued moving from left to right until all of the elements were in the desired order.

I'd iterate over the second sequence (the sorted list) and swap items in the first. I wrote this pseudo-code in python:

>>> a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>> b = [2, 4, 6, 7, 0, 1, 3, 5, 8, 9]

>>> def swap(seq, i, j):

...     a = seq[i]

...     seq[i] = seq[j]

...     seq[j] = a

...

>>> for index_in_b, value in enumerate(b):

...     index_in_a = a.index(value)

...     if index_in_b != index_in_a:

...         swap(a, index_in_a, index_in_b)

...         print('move {} to {}'.format(index_in_a, index_in_b))



move 0 to 2

move 1 to 4

move 2 to 6

move 3 to 7

move 4 to 6

move 5 to 6

move 6 to 7

In this case I'm moving the items in the first sequence by swapping them.

Update

We can slightly improve the performance in python by removing the move inside swap function and also removing the function call. Here is a performance comparison:

import timeit

s1 = """

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

b = [2, 4, 6, 7, 0, 1, 3, 5, 8, 9]

def swap(seq, i, j):

    a = seq[i]

    seq[i] = seq[j]

    seq[j] = a



for index_in_b, value in enumerate(b):

    index_in_a = a.index(value)

    if index_in_b != index_in_a:

        swap(a, index_in_a, index_in_b)"""



s2 = """

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

b = [2, 4, 6, 7, 0, 1, 3, 5, 8, 9]

for index_in_b, value in enumerate(b):

    index_in_a = a.index(value)

    if index_in_b != index_in_a:

        a[index_in_a], a[index_in_b] = a[index_in_b], a[index_in_a]"""





# on an i7 macbook pro

timeit.timeit(s1) 

4.087386846542358

timeit.timeit(s2)

3.5381240844726562

Slightly better, but for sure there are better ways to achieve this.