projecteuler.net

First Sort II

Published on Sunday, 6th September 2015, 07:00 am; Solved by 173;
Difficulty rating: 75%

Problem 524

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:
    • a. Move the smallest element of the pair at the beginning of the list.
    • b. 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)

Let F(L) be the number of times step 2a is executed to sort list L. For example, F({ 4 1 3 2 }) = 5.

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:

PI4(P)F(P)
{1, 2, 3, 4}10Q(4, 0) = 1
{1, 2, 4, 3}24Q(4, 4) = 2
{1, 3, 2, 4}32Q(4, 2) = 3
{1, 3, 4, 2}42
{1, 4, 2, 3}56Q(4, 6) = 5
{1, 4, 3, 2}64
{2, 1, 3, 4}71Q(4, 1) = 7
{2, 1, 4, 3}85Q(4, 5) = 8
{2, 3, 1, 4}91
{2, 3, 4, 1}101
{2, 4, 1, 3}115
{2, 4, 3, 1}123Q(4, 3) = 12
{3, 1, 2, 4}133
{3, 1, 4, 2}143
{3, 2, 1, 4}152
{3, 2, 4, 1}162
{3, 4, 1, 2}173
{3, 4, 2, 1}182
{4, 1, 2, 3}197Q(4, 7) = 19
{4, 1, 3, 2}205
{4, 2, 1, 3}216
{4, 2, 3, 1}224
{4, 3, 1, 2}234
{4, 3, 2, 1}243

Let R(k) = min(Q(n, k)) over all n for which Q(n, k) is defined.

Find R(1212).