Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

python - Most efficient method of sorting permutations of a list using the minimum number of insertions, removals or transpositions

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)
等待大神答复

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...