0%

Problem 524


Problem 524


First Sort II

Consider the following algorithm for sorting a list:

  1. Starting from the beginning of the list, check each pair of adjacent elements in turn.
  2. 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.
  3. 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. 从数列的起始位置开始,逐一比较每一对相邻的数。
  2. 如果相邻的数顺序有误:
    • 将其中较小的数移至数列的首位。
    • 回到第1步。
  3. 如果每一对相邻的数均已有序,算法结束。

例如,数列{ 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)。