Problem 524
First Sort II
Consider the following algorithm for sorting a list:
- Starting from the beginning of the list, check each pair of adjacent elements in turn.
- If the elements are out of order:
- Move the smallest element of the pair at the beginning of the list.
- Restart the process from step 1.
- If all pairs are in order, stop.
For example, the list { 4 1 3 2 } is sorted as follows:
- 4 1 3 2 (4 and 1 are out of order so move 1 to the front of the list)
- 1 4 3 2 (4 and 3 are out of order so move 3 to the front of the list)
- 3 1 4 2 (3 and 1 are out of order so move 1 to the front of the list)
- 1 3 4 2 (4 and 2 are out of order so move 2 to the front of the list)
- 2 1 3 4 (2 and 1 are out of order so move 1 to the front of the list)
- 1 2 3 4 (The list is now sorted)
We can list all permutations P of the integers {1, 2, …, n} in lexicographical order, and assign to each permutation an index In(P) from 1 to n! corresponding to its position in the list.
Let Q(n, k) = min(In(P)) for F(P) = k, the index of the first permutation requiring exactly k steps to sort with First Sort. If there is no permutation for which F(P) = k, then Q(n, k) is undefined.
For n = 4 we have:
| P | I4(P) | F(P) | |
|---|---|---|---|
| {1, 2, 3, 4} | 1 | 0 | Q(4, 0) = 1 |
| {1, 2, 4, 3} | 2 | 4 | Q(4, 4) = 2 |
| {1, 3, 2, 4} | 3 | 2 | Q(4, 2) = 3 |
| {1, 3, 4, 2} | 4 | 2 | |
| {1, 4, 2, 3} | 5 | 6 | Q(4, 6) = 5 |
| {1, 4, 3, 2} | 6 | 4 | |
| {2, 1, 3, 4} | 7 | 1 | Q(4, 1) = 7 |
| {2, 1, 4, 3} | 8 | 5 | Q(4, 5) = 8 |
| {2, 3, 1, 4} | 9 | 1 | |
| {2, 3, 4, 1} | 10 | 1 | |
| {2, 4, 1, 3} | 11 | 5 | |
| {2, 4, 3, 1} | 12 | 3 | Q(4, 3) = 12 |
| {3, 1, 2, 4} | 13 | 3 | |
| {3, 1, 4, 2} | 14 | 3 | |
| {3, 2, 1, 4} | 15 | 2 | |
| {3, 2, 4, 1} | 16 | 2 | |
| {3, 4, 1, 2} | 17 | 3 | |
| {3, 4, 2, 1} | 18 | 2 | |
| {4, 1, 2, 3} | 19 | 7 | Q(4, 7) = 19 |
| {4, 1, 3, 2} | 20 | 5 | |
| {4, 2, 1, 3} | 21 | 6 | |
| {4, 2, 3, 1} | 22 | 4 | |
| {4, 3, 1, 2} | 23 | 4 | |
| {4, 3, 2, 1} | 24 | 3 |
Let R(k) = min(Q(n, k)) over all n for which Q(n, k) is defined.
Find R(1212).
首位排序 II
考虑如下的数列排序算法：
- 从数列的起始位置开始，逐一比较每一对相邻的数。
- 如果相邻的数顺序有误：
- 将其中较小的数移至数列的首位。
- 回到第1步。
- 如果每一对相邻的数均已有序，算法结束。
例如，数列{ 4 1 3 2 }的排序过程如下：
- 4 1 3 2 （4和1顺序有误，将1移至数列的首位）
- 1 4 3 2 （4和3顺序有误，将3移至数列的首位）
- 3 1 4 2 （3和1顺序有误，将1移至数列的首位）
- 1 3 4 2 （4和2顺序有误，将2移至数列的首位）
- 2 1 3 4 （2和1顺序有误，将1移至数列的首位）
- 1 2 3 4 （数列排序完毕）
我们可以将数集{1, 2, …, n}的所有排列P按照字典序排成一列，并根据该排列在字典序中的位置给每个排列指定一个指数In(P)为1至n!。
对于所有F(P)=k，记Q(n, k) = min(In(P))，也就是首位排序完成时需要将数移至首位k次的第一个排列的指数。如果不存在排列使得F(P) = k，则Q(n, k)记为未定义。
对于n = 4我们有：
| P | I4(P) | F(P) | |
|---|---|---|---|
| {1, 2, 3, 4} | 1 | 0 | Q(4, 0) = 1 |
| {1, 2, 4, 3} | 2 | 4 | Q(4, 4) = 2 |
| {1, 3, 2, 4} | 3 | 2 | Q(4, 2) = 3 |
| {1, 3, 4, 2} | 4 | 2 | |
| {1, 4, 2, 3} | 5 | 6 | Q(4, 6) = 5 |
| {1, 4, 3, 2} | 6 | 4 | |
| {2, 1, 3, 4} | 7 | 1 | Q(4, 1) = 7 |
| {2, 1, 4, 3} | 8 | 5 | Q(4, 5) = 8 |
| {2, 3, 1, 4} | 9 | 1 | |
| {2, 3, 4, 1} | 10 | 1 | |
| {2, 4, 1, 3} | 11 | 5 | |
| {2, 4, 3, 1} | 12 | 3 | Q(4, 3) = 12 |
| {3, 1, 2, 4} | 13 | 3 | |
| {3, 1, 4, 2} | 14 | 3 | |
| {3, 2, 1, 4} | 15 | 2 | |
| {3, 2, 4, 1} | 16 | 2 | |
| {3, 4, 1, 2} | 17 | 3 | |
| {3, 4, 2, 1} | 18 | 2 | |
| {4, 1, 2, 3} | 19 | 7 | Q(4, 7) = 19 |
| {4, 1, 3, 2} | 20 | 5 | |
| {4, 2, 1, 3} | 21 | 6 | |
| {4, 2, 3, 1} | 22 | 4 | |
| {4, 3, 1, 2} | 23 | 4 | |
| {4, 3, 2, 1} | 24 | 3 |
对于所有Q(n, k)有定义的n，记R(k) = min(Q(n, k))。
求R(1212)。