Python Forum
Order a list with successive permutations based on another list
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Order a list with successive permutations based on another list
#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!
Reply
#2
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?
Reply
#3
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]
Reply
#4
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.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Compile list of dictianories out of another list of dictianories by certain keys CatorCanulis 10 644 Jun-10-2021, 08:35 PM
Last Post: perfringo
  Saving list in a list quest_ 3 740 Mar-10-2021, 09:58 AM
Last Post: quest_
Star Convert Bytearray into List using list() Shlok 2 508 Feb-18-2021, 10:44 AM
Last Post: deanhystad
  Group List Elements according to the Input with the order of binary combination quest_ 19 1,416 Jan-28-2021, 03:36 AM
Last Post: bowlofred
  What happens to a <itertools.permutations object at 0x7fe3cc66af68> after it is read? Pedroski55 3 445 Nov-29-2020, 08:35 AM
Last Post: DeaD_EyE
  Adding List Element if Second part of the List Elements are the Same quest_ 3 624 Nov-25-2020, 04:33 PM
Last Post: bowlofred
  Count number of occurrences of list items in list of tuples t4keheart 1 576 Nov-03-2020, 05:37 AM
Last Post: deanhystad
Question Save list with nested list into CSV SpongeB0B 1 1,137 Oct-12-2020, 07:26 AM
Last Post: bowlofred
  Appending to list of list in For loop nico_mnbl 2 580 Sep-25-2020, 04:09 PM
Last Post: nico_mnbl
  How to make a list of values from a dictionary list? faryad13 2 652 Sep-03-2020, 03:45 PM
Last Post: faryad13

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020