Python Forum
Order a list with successive permutations based on another list - Printable Version

+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: Order a list with successive permutations based on another list (/thread-32940.html)

Order a list with successive permutations based on another list - yvrob - Mar-17-2021

Hi everybody,

I am running into a problem that seems rather simple but here is what I need to do:
I have an initial list, say: L = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
I have an order list, say: o = [9 ,1 ,2 ,5 ,7 ,3 ,10 ,8 , 4, 6]

My goal is to sort L based on the order list. So for my simple listL, it would become the same as o.
Where the difficult comes is that I would like to do that only by swapping members of the list L.

My attempt to do that was the following:

for i in range(len(l)):
    print('Swapping {} and {}'.format(i+1, order[i]))
    tmp = l[i]
    l[i] = l[order[i]-1]
    l[order[i]-1] = tmp
    print(l)
The problem is that what I end up with for this simple example is [ 2, 3, 6, 1, 7, 4, 10, 8, 5, 9]

Would you have any suggestion? I really need to keep the swapping part.

Thanks!

RE: Order a list with successive permutations based on another list - yvrob - Mar-17-2021

Side question to this: I really need not to loose the information of L (it will be objects instead of numbers at some point). But also, the memory needed for such calculation will be very large, almost the available memory I have.

So I wanted to swap elements, but would there be a more efficient way, taking little memory (so no complete copy of the list L possible), that would work?

It seems that my algorithm scales to the square of the number of elements in L, and from my preliminary results the calculation would need 27 hours to run with 500,000 elements.

Any idea?

RE: Order a list with successive permutations based on another list - menator01 - Mar-18-2021

Not really sure what you're looking for but this checks if L is in O then appends to new list.
L = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
O = [9 ,1 ,2 ,5 ,7 ,3 ,10 ,8 , 4, 6]

ordered_list = []

for i in O:
    if i in L:
        ordered_list.append(i)

print(ordered_list)
Output:
[9, 1, 2, 5, 7, 3, 10, 8, 4, 6]


RE: Order a list with successive permutations based on another list - supuflounder - Mar-19-2021

I think part of your problem is that you have used a dense set of integers for each list, which makes it hard to see what is going on. I would suggest choosing some random values for L, just type in whatever numbers you feel like, or better still, use letters like
ML= ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J"]
L = ML
O = [9 ,  1 ,  2 ,  5 ,  7 ,  3 , 10 ,  8 ,  4,   6]
R = []
for i in O:
   R.append(L[i-1])
print("Build list result: ", R)

print("Start ", L)
for i in range(len(L)):
   tmp = L[i]
   # O[0] = 9, L[0] = "A", L[9] = "I" 
   print("{}:  O[{}] = {}. L[{}] = {}".format(i, i,  O[i], O[i] - 1, L[O[i] - 1] ) )
   L[i] = L[O[i] - 1]
   L[O[i] - 1] = tmp
   print("L:    ", L)
   print("R:    ", R)
   print()
The problem with your swapping method is that once you move "I" to location 0 and swap "A" to location 9, then when you select element 1, that is, index 0, you are selecting the value "I", which is what you put in location 0.

The output shows what happens if I print the correct solution below what your algorithm computes. Note how it just completely loses track of what is going on.
Output:
Build list result:  ['I', 'A', 'B', 'E', 'G', 'C', 'J', 'H', 'D', 'F']
Start  ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
0:  O[0] = 9. L[8] = I
L:     ['I', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'A', 'J']
R:     ['I', 'A', 'B', 'E', 'G', 'C', 'J', 'H', 'D', 'F']

1:  O[1] = 1. L[0] = I
L:     ['B', 'I', 'C', 'D', 'E', 'F', 'G', 'H', 'A', 'J']
R:     ['I', 'A', 'B', 'E', 'G', 'C', 'J', 'H', 'D', 'F']

2:  O[2] = 2. L[1] = I
L:     ['B', 'C', 'I', 'D', 'E', 'F', 'G', 'H', 'A', 'J']
R:     ['I', 'A', 'B', 'E', 'G', 'C', 'J', 'H', 'D', 'F']

3:  O[3] = 5. L[4] = E
L:     ['B', 'C', 'I', 'E', 'D', 'F', 'G', 'H', 'A', 'J']
R:     ['I', 'A', 'B', 'E', 'G', 'C', 'J', 'H', 'D', 'F']

4:  O[4] = 7. L[6] = G
L:     ['B', 'C', 'I', 'E', 'G', 'F', 'D', 'H', 'A', 'J']
R:     ['I', 'A', 'B', 'E', 'G', 'C', 'J', 'H', 'D', 'F']

5:  O[5] = 3. L[2] = I
L:     ['B', 'C', 'F', 'E', 'G', 'I', 'D', 'H', 'A', 'J']
R:     ['I', 'A', 'B', 'E', 'G', 'C', 'J', 'H', 'D', 'F']

6:  O[6] = 10. L[9] = J
L:     ['B', 'C', 'F', 'E', 'G', 'I', 'J', 'H', 'A', 'D']
R:     ['I', 'A', 'B', 'E', 'G', 'C', 'J', 'H', 'D', 'F']

7:  O[7] = 8. L[7] = H
L:     ['B', 'C', 'F', 'E', 'G', 'I', 'J', 'H', 'A', 'D']
R:     ['I', 'A', 'B', 'E', 'G', 'C', 'J', 'H', 'D', 'F']

8:  O[8] = 4. L[3] = E
L:     ['B', 'C', 'F', 'A', 'G', 'I', 'J', 'H', 'E', 'D']
R:     ['I', 'A', 'B', 'E', 'G', 'C', 'J', 'H', 'D', 'F']

9:  O[9] = 6. L[5] = I
L:     ['B', 'C', 'F', 'A', 'G', 'D', 'J', 'H', 'E', 'I']
R:     ['I', 'A', 'B', 'E', 'G', 'C', 'J', 'H', 'D', 'F']

Press any key to continue . . .
So you have to remember that the value that was input location 0 is now in input location 8. This involves a "bookkeeping" array. Now if the elements of L are complex objects, a bookkeeping array of integers is probably smaller than a copy of the elements as formed in R. But that is pretty complicated.

A few more print statements would have helped you understand what is going on in your sort.