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]
I welcome all feedback.
The only dumb question, is one that doesn't get asked.
My Github
How to post code using bbtags


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
  unable to remove all elements from list based on a condition sg_python 3 373 Jan-27-2024, 04:03 PM
Last Post: deanhystad
  Copying the order of another list with identical values gohanhango 7 1,062 Nov-29-2023, 09:17 PM
Last Post: Pedroski55
  No matter what I do I get back "List indices must be integers or slices, not list" Radical 4 1,091 Sep-24-2023, 05:03 AM
Last Post: deanhystad
  Why do I have to repeat items in list slices in order to make this work? Pythonica 7 1,257 May-22-2023, 10:39 PM
Last Post: ICanIBB
  Delete strings from a list to create a new only number list Dvdscot 8 1,466 May-01-2023, 09:06 PM
Last Post: deanhystad
  List all possibilities of a nested-list by flattened lists sparkt 1 878 Feb-23-2023, 02:21 PM
Last Post: sparkt
  Сheck if an element from a list is in another list that contains a namedtuple elnk 8 1,713 Oct-26-2022, 04:03 PM
Last Post: deanhystad
Question Keyword to build list from list of objects? pfdjhfuys 3 1,499 Aug-06-2022, 11:39 PM
Last Post: Pedroski55
  Split a number to list and list sum must be number sunny9495 5 2,196 Apr-28-2022, 09:32 AM
Last Post: Dexty
  select Eof extension files based on text list of filenames with if condition RolanRoll 1 1,475 Apr-04-2022, 09:29 PM
Last Post: Larz60+

Forum Jump:

User Panel Messages

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