Order a list with successive permutations based on another list

Python Help
1

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!

3

Hello, and thank you for your help.
Unfortunately, I have to go through the implementation myself.

But I will check the code.

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?

4

If you really need to implement the swapping yourself instead of relying on any libraries or a built-in method, then here’s a trick. To sort the initial list based on the order list, you should sort the order list from smallest to largest using swaps and use the same swaps for the initial list. Here’s a simple example.

initial_list = [1, 2, 3, 4]
order_list = [2, 1, 4, 3]

Step 1: Swap order_list[0] and order_list[1]. Do the same for initial_list.

order_list[0], orderlist[1] = order_list[1], orderlist[0]
initial_list[0], initial_list[1] = initial_list[1], initial_list[0]

Step 2: Swap order_list[2] and order_list[3]. Do the same for initial_list.

order_list[2], orderlist[3] = order_list[3], orderlist[2]
initial_list[2], initial_list[3] = initial_list[3], initial_list[2]

Now that order_list has been sorted fully from smallest to largest, initial_list will have been sorted based on order_list. Checking the values, we find that initial_list is now [2, 1, 4, 3] and order_list is [1, 2, 3, 4].

This technique will work even if initial_list is a list of objects. As for figuring out which sequence of swaps to do, you can implement quicksort, which has runtime O(n log n) for a list of size n. Using quicksort, you can sort order_list one swap at a time and just apply the same swap at each step to initial_list.

1 Like
5

Thank you for this interesting point.

I tried something like this:

import numpy as np
from random import sample

N = 10

l0 = np.array([i for i in range(1,N+1)])
l = np.array(list(l0))
order0 = np.array(sample(range(1,N+1), N)) # ORDER
order = np.array(list(order0))

for i in range(len(order)): 
    min_idx = i 
    for j in range(i+1, len(order)): 
        if order[min_idx] > order[j]: 
            min_idx = j 
    tmp = order[i] 
    order[i] = order[min_idx]
    order[min_idx] = tmp
    
    tmp = l[i] 
    l[i] = l[min_idx]
    l[min_idx] = tmp

print('Initial l=', l0)
print('Initial order=', order0)
print('Final l=', l)
print('Final order=', order)

Unfortunately, I don’t get the results I would like to have (order0=l at the end for this example). I took the sorting algorithm on geekforgeeks.
Do you know why in my example it does not work?

EDIT: My next attempt was the following, taken from another website, and it is still not working, I have no clue why.

arr = [1,2,3,4,5,6,7,8,9,10]
index = [3, 7,9, 8, 0, 4, 1, 2, 6, 5]

c =0
for i in range(len(arr)):
arr[index[c]],arr[c] = arr[c],arr[index[c]]
index[index[c]], index[c] = index[c],index[index[c]]
if index[c]==c:
    c=c+1
print(arr)
6

I see what the problem is; I misinterpreted what the order list is supposed to do in my original solution. My original solution assumed that if the first number in the order list is 8, then you want the first element of the initial list to become the 8th element of the final list. Instead, you want the 8th element of the original list to become the 1st element of the final list. This changes the algorithm that needs to be done.

The simplest solution I can think of doesn’t involve swaps at all; it just constructs a new list. To simplify the code, I’ll start counting from 0 since Python indices start at 0. This solution uses O(n) memory (because of the extra list that’s created) and has runtime O(n) (because you just do a single pass through order_list).

original_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
order_list = [4, 8, 9, 1, 2, 5, 7, 0, 6, 3]
final_list = [original_list[i] for i in order_list]

If you must do the sorting by making swaps in the original list, then the idea would be to sort the original list based on the index of the corresponding element in the order list. The following code does that and should still work even if original_list is a list of objects. This solution takes O(n) memory (because of the creation of order_list_map and that each element of original_list needs to be tagged with its target index) and has runtime O(n log n) (because of the sorting algorithm that’s used).

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

# precompute a dictionary that can be used to quickly find the index of
# an element in order_list
order_list_map = {v:k for k,v in enumerate(order_list)}

# tag each element of original_list with the index where it needs to end up
for i in range(len(original_list)):
    original_list[i] = (original_list[i], order_list_map[i])

# Sort original_list based on the tagged index.  I'm using the built-in sort() method, 
# but you can implement your own sorting algorithm that does all the swaps manually.
original_list.sort(key=lambda x: x[1])

# Now that the list has been sorted, remove the tagged indices if you want
for i in range(len(original_list)):
    original_list[i] = original_list[i][0]
7

Thank you very much, that works way better!

Now, I would like to do it several times. Let’s say that I have a table of size 5 corresponding to each object’s spatial location. This location varies with time, described by the order_list depending on the step. And to make it simple here we will take:
Step 0: [0,1,2,3,4]
Step 1: [4,0,1,2,3]
Step 2: [3,4,0,1,2]
Step 3: [2,3,4,0,1]
…
Which means that for example, at the step 2 and the location 0, I want to have the value original_list[3], and at the step 3 at the same location I wil have original_list[2], etc.

My problem is that at the beginning the original_list is sorted (as in the example above), but then after the first step, my original list looks like that: [4,0,1,2,3] and after the next switch it should look like [3,4,0,1,2].

I think that an intermediary step is needed, but I can’t find it. Would you have any idea here?

EDIT: here is my code:
import numpy as np
from random import sample

N = 5

original_list = [i for i in range(0,N)]
for K in range(5):
    order_list = sample(range(0,N), N) # ORDER
    print('Step',K)
    print('Original',original_list)
    print('Order',order_list)
    
    order_list_map = [np.nan for i in range(N)]
    for i in range(N):
        order_list_map[order_list[i]] = i
    
    # print(order_list_map)
    
    for i in range(len(order_list_map)): 
        min_idx = i 
        for j in range(i+1, len(order_list_map)): 
            if order_list_map[min_idx] > order_list_map[j]: 
                min_idx = j 
        tmp = order_list_map[i] 
        order_list_map[i] = order_list_map[min_idx]
        order_list_map[min_idx] = tmp
        
        tmp = original_list[i] 
        original_list[i] = original_list[min_idx]
        original_list[min_idx] = tmp
        
    print('Final',original_list)
    
    if all([order_list[i]==original_list[i] for i in range(N)]):
        print('---> Same order')
    else:
        print('---> Wrong order')

And the output:

Step 0
Original [0, 1, 2, 3, 4]
Order [2, 0, 1, 3, 4]
Final [2, 0, 1, 3, 4]
---> Same order
Step 1
Original [2, 0, 1, 3, 4]
Order [2, 1, 3, 4, 0]
Final [1, 0, 3, 4, 2]
---> Wrong order
Step 2
Original [1, 0, 3, 4, 2]
Order [0, 3, 2, 4, 1]
Final [1, 4, 3, 2, 0]
---> Wrong order
Step 3
Original [1, 4, 3, 2, 0]
Order [3, 2, 1, 4, 0]
Final [2, 3, 4, 0, 1]
---> Wrong order
Step 4
Original [2, 3, 4, 0, 1]
Order [3, 1, 0, 4, 2]
Final [0, 3, 2, 1, 4]
---> Wrong order
8

The current code assumes that at each step, order_list describes how to sort original_list relative to its current order. You are seeking a way to sort the list in such a way so that order_list is relative to the original order.

The general idea here would be to figure out what sequence of swaps would be necessary to get from one order_list to the next. In step 2 of your example above, you’ll need to calculate what swaps are needed to get from [4,0,1,2,3] to [3,4,0,1,2] and apply the same swaps to the original list.

As for writing the code that does this, you can pull ideas from the code I’ve already written. In the example code I gave, one interpretation is that I am calculating the sequence of swaps necessary to get from [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] to [4, 8, 9, 1, 2, 5, 7, 0, 6, 3] and performing those swaps. Try to adapt the code to your situation; figure out what swaps are necessary to get from each order_list to the next order_list at each step, applying the swaps to original_list as you go.

9

Hello, I had a break from my project, so I am coming back to it now.
Aohan Dang thank you very much for your help.

I could make it work but doing the following:

  • I have old_order, new_order at each step.
  • I build a transition array, and then I “map” this transition array:
for i in range(len(order):
        for j in range(len(order)):
            if old_order[i] == order[j]:
                transition[i] = j
        transition_map[transition[i]] = i
  • Then I sort the transition_map array

And this works very well! The only thing is that the size of my lists is very heavy, meaning that the time taken to complete this process is huge (the swapping process is pretty time-consuming, but I guess that it is the only solution for saving memory).
The good thing is that I have access to computers in parallel.

So let’s say that computer0 has objects 1 to 3, computer1 has objects 4 to 6 and computer2 has objects 7 to 9. Computer0 has no idea of what objects 3 to 8 are, the only thing it knows it that they exist and which computer they belong to. There are then two cases:

  • Objects stay in their respective computers when sorted (ex:[1,2,3,4,5,6,7,8,9] → [2,3,1,4,6,5,9,8,7]) From my understanding, loading old_order, order, then computing transition and transition_map and just adding a condition that they belong to the computer currently used and applying the sorting algorithm works. Basically each computer individually sorts its own objects and it ends up correct.
  • Objects can change from one computer to another (ex:[1,2,3,4,5,6,7,8,9] → [1,2,4,3,8,7,5,9,6]).
    Here, I am kind of stuck. My idea is to store data from object leaving each computer in separate files (cmp1: 3, cmp2: 4,5,6, cmp3: 7,8), then import the data for each computer and preliminarily replace the objects leaving the computer by the objects entering the computer. It does not seem to end up with the right order.

Have you already been facing a problem like that? Any suggestion would be welcome!