如何找到最小开关数以按升序对给定的排列（比方说 1-10）进行排序

Question

亚瑟王的书架上有 10 本书，编号为 1,2,3,...,10。多年来，卷变得混乱。 Arthur 试图通过同时交换两本书的位置来按升序排列这些书。由于书很重，他每天只能换两册。帮梅林订书。

例如，如果一个排列是 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 那么我们只需要 5 个开关来按升序排序

注意：最坏情况下会有9个开关

Q1。求最坏情况对应的排列

Q2。如何找到给定排列所需的最少开关数。（算法和如果可能的话用 C、C++、python 中的任何一个编写的代码）

PS：我能够手动解决它，最好说是 Trial N 错误（对 Q1.10、1、2、3、4、5、6、7、8、9 的回答）。但我想知道算法

Answer 1

使用 1 索引列表，

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

[0,10,9,8,7,6,5,4,3,2,1] # 前面加0使list 1-indexed

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

Step2: 运行一个while循环直到迭代器值大于0

Step3:如果迭代器中的元素匹配到值，那么我们必须减少迭代器的值，因为不需要执行交换操作。

Step4:如果元素不匹配，则将元素与其索引值交换并将操作计数加1。无需递减迭代器值，因为在这种情况下，我们在迭代器位置获得的值可能与其索引不匹配...

解决方案的时间复杂度为 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)

Answer 2

所需的最小交换次数等于元素总数减去permutation cycles的数量。最坏的情况似乎是一个周期。我们可以通过将自然顺序向下或向上移动一次来获得它的排列（例如，1 2 3 -> 2 3 1 或 3 1 2）。

例如：

1 2 3 4 5
2 5 4 3 1

Start with 1 and follow the cycle:
1 down to 2, 2 down to 5, 5 down to 1.

1 -> 2 -> 5 -> 1
3 -> 4 -> 3

我们需要将索引 1 与 5 交换，然后将索引 5 与 2 交换；以及索引 3 和索引 4。总共 3 次交换或 n - 2.

我们用循环数减去 n，因为循环元素加起来总计 n，每个循环表示交换小于其中的元素数。

例如：

 1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

1 -> 10 -> 1
2 -> 9 -> 2
3 -> 8 -> 8
4 -> 7 -> 4
5 -> 6 -> 5

排列周期：

(10 1)(9 2)(8 3)(7 4)(6 5)

Q1 = num_elements - num_cycles
   = 10 - 5
   = 5

为了得到最坏的情况（Q2），将自然顺序向下或向上移动一次。比如向下移动1：

1  2  3  4  5  6  7  8  9 10
2  3  4  5  6  7  8  9 10  1

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 1

Permutation cycles (just one):

(2 3 4 5 6 7 8 9 10 1)

或向上移动 1：

 1  2  3  4  5  6  7  8  9 10
10  1  2  3  4  5  6  7  8  9

1 -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

Permutation cycles (just one):

(10 9 8 7 6 5 4 3 2 1)

结果：

Q2 = num_elements - num_cycles
   = 10 - 1
   = 9

如何找到最小开关数以按升序对给定的排列（比方说 1-10）进行排序

How to find minimum number of switches to sort a given permutation(let's say 1-10) in ascending order

python-3.x

algorithm

sorting

permutation

discrete-mathematics