如何找到最小数量的开关以升序对给定排列(例如1-10)进行排序 [英] How to find minimum number of switches to sort a given permutation(let's say 1-10) in ascending order

问题描述

亚瑟王的书架上有10本书，编号分别为1,2,3，...，10.多年来，交易量变得混乱.Arthur试图通过一次交换两本书的位置来按升序对书籍进行排序.由于书籍很重，他每天只能切换两卷.帮助Merlin订购书籍.

King Arthur has a shelf with 10 books, numbered 1,2,3,...,10. Over the years, the volumes got disordered. Arthur tries to order the books in the increasing order by exchanging positions of two books at once. Since the books are heavy, he can only switch two volumes each day. Help Merlin to order the books.

例如，如果排列是10、9、8、7、6、5、4、3、2、1，那么我们只需要5个开关即可将其升序排列

E.g If a permutation is 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 then we need just 5 switches to sort it in ascending order

注意:在最坏的情况下，将有9个开关

Note: in the worst case there will be 9 switches

Q1.找到与最坏情况对应的排列

Q1. Find the permutation corresponding to the worst case

Q2.如何找到给定排列所需的最少开关数.(如果可能，可以使用C，C ++，python中的任何一种算法和算法)

Q2. How to find the minimum number of switches required for a given permutation. (Algorithm & if possible code in either of C, C++, python)

PS:我能够手动解决此问题，最好说是Trial N错误(对Q1.10、1、2、3、4、5、6、7、8、9的回答).但我想知道算法

PS: I was able to solve it manually, better say Trial N error ( Answer to Q1. 10, 1, 2, 3, 4, 5, 6, 7, 8, 9). but I wish to know the algorithm

推荐答案

使用1索引列表，

在问题中给出的示例中，获取包含相同元素的列表:

Taking a list containing the same elements in an example given in the question:

[0,10,9,8,7,6,5,4,3,2,1]#在前面添加0以使列表1索引

[0,10,9,8,7,6,5,4,3,2,1] # Added 0 in front to make list 1-indexed

第1步:以列表的最后一个索引...作为迭代器

Step1: take the last index of the list... as an iterator

第2步:运行while循环，直到迭代器值大于0

Step2: Running a while loop until the iterator value is greater than 0

第3步::如果迭代器上的元素与值匹配，那么我们就必须减小迭代器的值，因为无需执行交换操作.

Step3: If the element at the iterator matches to the value, then we have to decrement the value of the iterator as no need to perform swap operation.

第4步:如果元素不匹配，则将元素与其索引值交换，并将操作计数增加1.一种情况是我们在迭代器位置获得的值可能与其索引不匹配...

Step4: If the element doesn't match, then swap the element with its index's value and increment the count of operations by 1. There is no need to decrement the iterator value as it might be a case that the value we got at the iterator's position might not be matching with its index...

解决方案的时间复杂度为O(2 * N)~~ O(N).

Time Complexity of the Solution is O(2*N) ~~ O(N).

arr = [0,10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
iterator = 10
count_of_operations = 0
while(iterator>0):
    index_to_swap = arr[iterator]
    if(index_to_swap == iterator):
        iterator = iterator - 1
    else:
        arr[iterator],arr[index_to_swap] = arr[index_to_swap],arr[iterator]
        count_of_operations = count_of_operations + 1
        
print(count_of_operations)

这篇关于如何找到最小数量的开关以升序对给定排列(例如1-10)进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！