I have written a function that takes two permutations of a list as arguments, and then attempts to sort one to match the other in the minimum number of moves possible and thus the shortest time.
This question comes in two parts:
Q1 - Is this the most efficient way of solving this problem in Python, or at least an efficient way?
Q2 - Is this just a high level method of implementing the swap item method of permutation? So at a lower level is Python handling the item swapping or is something else happening entirely?
Here is the function:
final_changes = []
def get_list_changes(list1, list2, r=0):
# Set up the global final_changes list
global final_changes
if r == 0:
final_changes = []
changes = []
# First get the index of items in both lists
for index, (first, second) in enumerate(zip(list1, list2)):
if first != second:
old_index = list1.index(second)
changes.append([index, old_index])
# Then get the index of the biggest index change
diff = [abs(change[0] - change[1]) for change in changes]
index = diff.index(max(diff))
# Make a copy of the second list and make that change
updated = list(list2)
updated.insert(changes[index][1], updated.pop(changes[index][0]))
final_changes.append(changes[index])
if list1 == updated:
return final_changes
else:
return get_list_changes(list1, updated, r + 1)
Here is some research I have read regarding calculating permutations:
https://www.geeksforgeeks.org/minimum-number-of-given-operations-required-to-convert-a-permutation-into-an-identity-permutation/
https://cstheory.stackexchange.com/questions/4096/minimum-number-of-transpositions-to-sort-a-list
Number of swaps in a permutation
How to find minimum number of switches to sort a given permutation(let's say 1-10) in ascending order
I have written a short test which takes a list of lists, each with an input list and the number of swap cycles that would be needed to put it in order. It then runs the function on the list and outputs if it's less or more than the swapping method and the number of changes for each. It seems to be split between sometimes needing more operations and sometimes needing less, depending on the number and types of changes.
ORIGINAL = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
INPUT = [
[[10, 1, 2, 3, 4, 5, 6, 7, 8, 9], 5],
[[1, 2, 3, 4, 5, 6, 10, 8, 9, 7], 1],
[[1, 3, 4, 5, 6, 2, 7, 9, 8, 10], 4],
[[10, 9, 8, 7, 6, 5, 4, 3, 2, 1], 5]
]
for lists in INPUT:
changes = get_list_changes(ORIGINAL, lists[0])
if len(changes) < lists[1]:
print('Less changes')
elif len(changes) == lists[1]:
print('Equal changes')
else:
print('More changes')
print(len(changes))
print(lists[1])
OUTPUT:
Less changes
1
5
More changes
2
1
Less changes
2
4
More changes
9
5
This is more a general question as to if anyone has used this or a similar method, how efficient it is and what exactly is happening at a lower level. On an intellectual level I'm interested to gather people's opinions and insights on to this propsed solution of solving an old mathematical problem.
