"K-transformed" permutations

Question

I have been banging my head against this problem for days, and searched exhaustively online for any hints on how to solve it. If you enjoy mathematically oriented programming problems, please take a look!

Here is the problem (PDF courtesy of UVA):

Consider a sequence of n integers < 1 2 3 4 ... n >. Since all the values are distinct, we know that there are n factorial permutations. A permutation is called K-transformed if the absolute difference between the original position and the new position of every element is at most K. Given n and K, you have to find out the total number of K-transformed permutations.

...

Input: The first line of input is an integer T (T < 20) that indicates the number of test cases. Each case consists of a line containing two integers n and K. (1 <= n <= 10^9) and (0 <= K <= 3).

Output: For each case, output the case number first followed by the required result. Since the result could be huge, output result modulo 73405.

The problem setter, Sohel Hafiz, categorized this problem as "Fast Matrix Exponentiation." Unfortunately, the google search I linked here doesn't appear to bring up any relevant links besides a Wikipedia page thick with mathematical jargon and notation (Wikipedia has proven to me to be a poor replacement for any math textbook).

Here's what I've done so far:

This code will compute by recursion the number of K-transformed permutations for low values of n and k, but is far too complex. It is good enough to build a table for searching for patterns:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int permute(int * a, int size, int i, int k)
{
  int j;
  int total = 0;
  int x = size-i;
  int low=0;
  int high=size;
  if (i == 0)
  {
/*    for (j=0;j<size;j++)
      printf("%d, ", a[j]);
    printf("\n");
*/    return 1;
  }
  if (x-k>0)
    low = x-k;
  if (x+k+1<size)
    high = x+k+1;
  for (j=low;j<high;j++)
  {
    int b[size];
    memcpy(b,a,size*sizeof(int));
    if (b[j] == 0)
    {
      b[j] = x+1;
      total += permute(b,size,i-1,k);
    }
  }
  return total;
}

int main() 
{
  int n, k, j, y, z;
  int * arr;
  /*scanf("%d %d", &n,&k);*/ k=2;
  for (n=0;n<14;n++)
  {
    int empty[n];
    for (j=0;j<n;j++)
      empty[j] = 0;
    arr = empty;  
    z = permute(arr, n, n, k);
    y = magic(n,k);
    printf("%d %d\n",z, y);
  }
  return 0;
}

The first thing I figured out was that k=1 is clearly the Fibonacci sequence. The magic function in main here is something I figured out later, almost by accident. It works ONLY for k=2, but it is exact up to n=14.

int magic(int n, int k)
{
  if (n<0)
    return 0;
  if (n==0)
    return 1;
  if (n==1)
    return 1;
  return 2*magic(n-1,k) + 2*magic(n-3,k) - magic(n-5,k);  
}

Very weird! I don't know the significance of this function, but it can be simplified to run in a loop in order to run just fast enough to finish K=2 for values up to 10^9.

All that's remaining is to find a non-recursive equation that can find any value for K=3 in a reasonable amount of time (under 10s).

EDIT: I am interested in the algorithm used to solve the problem for any given n and k within a reasonable amount of time. I do not expect anyone to actually confirm that their algorithm works by writing code to the specifications of the contest rules, what I'm looking for in an answer is a description of how to approach the problem and apply numerical methods to reach a solution.

Answer 1

There are two parts to the problem. First is figuring out the recurrence formula for k=0, 1, 2, 3. The second part is calculating values for large n using the recurrence formula.

For the first part:

Let p(n, k) be the number of permutations of n elements that are k-transformed. When k=0 the recurrence is just p(n, 0) = 1.

For k=1, first consider where 1 goes in the permutation. It either goes in position 1 or position 2. If it goes in position 1, then the remaining elements are just the original problem with n-1 elements. So we have p(n, 1) = p(n-1, 1) + .... If the first element goes in position 2, then what? In this case the second element has to go into position 1. At this point you have the original problem with n-2 elements. So the recurrence is p(n, 1) = p(n-1, 1) + p(n-2, 1) which is the Fibonacci sequence.

For k=2 and k=3 you get more possibilities but the reasoning is the same. [still working out exact recurrences]

The second part is computing the solution to the recurrences for large values of n. For this you put the recurrence into matrix form and do repeated squaring/multiplying to get high powers of the matrix. For the k=1 case the matrix is:

A = [0 1]
    [1 1]

To get p(n + 2, 1) you need to compute A^n * [1, 1].

Answer 2

Since K is low, it falls naturally on matrix exponentiation.

Each item can end up at most K positions from it's start position. This gives at most (2 K - 1) positions, but some positions could already be occupied. You can have 2^{2 K - 1} possible configurations (of the closest (2 K -1) slots) when placing an item. Each new item in any unoccupied position would generate a new configuration, and a new, and a new...

You need to figure out how many ways you can get from each configuration to every other. You could use brute force for this, and save the values. When you know this, you can place the numbers in a matrix; Every column is the from-configuration, and every row is the to-configuration.

Consider a count-vector v; Each cell in it represents the number of ways to get to some configuration in n steps. Start with the initial count-vector (all zeros, except for one 1 representing the empty configuration, n = 0). If you multiply this vector with the matrix (v x A), you will move those counts ahead one step (n = 1). Repeat for additional steps.

Now comes the interesting part. If you multiply this matrix with itself (A x A), you will get a matrix for moving two generations ahead. Again (A² x A²) and you will get a matrix for moving 4 generations. You can use this technique to move it several thousand (or million) generations ahead, in just a few iterations.

You can read more about exponentiation by squaring on Wikipedia.

---

If the above is too slow, you can try to find a recurrence relation for the values you find. Take the first few values of the sequence, and place them in an equation system:

a · x₁ + b · x₂ = x₃
a · x₂ + b · x₃ = x₄

Solve for a and b. Then to generate the sequence, you multiply the last two numbers with a and b and add to get the next.

If this doesn't reproduce the sequence, you can increase the size:

a · x₁ + b · x₂ + c · x₃ = x₄
a · x₂ + b · x₃ + c · x₄ = x₅
a · x₃ + b · x₄ + c · x₅ = x₆

Solve for a, b and c. Increase further until you get something that works. If you go one more step then, you should get an under-determined system.

It could happen that there are no recurrence relation (at least no linear one). In this case you could increase size, but you would never find anything that works.

---

To take a simple example. Let's consider K = 1. This will give us a neighborhood of size 3 (= 2 K + 1), and 8 distinct configurations (= 2^{2 K + 1}).

To pick a notation, I'll use # for occupied or inaccessible, and . for free.

To generate the matrix, we must consider which patterns can be transformed into which by adding a single symbol.

• For patterns starting with a free slot, we must place the next symbol to the far left. Otherwise we would have a gap in the sequence.

• For the pattern ###, we don't have any free spaces to place anything, so that is a dead-end.

• For the remaining patterns, can can place a symbol in any free spot, and then shift the pattern one space (moving to the next position).

The matrix could look like this:

    ... ..# .#. .## #.. #.# ##. ###
...  1   0   0   0   0   0   0   0
..#  0   0   1   0   0   0   0   0
.#.  0   0   0   0   1   0   0   0
.##  0   0   0   0   0   0   1   0
#..  0   0   1   0   1   0   0   0
#.#  0   0   0   0   0   0   1   0
##.  0   0   0   0   0   0   1   0
###  0   0   0   0   0   0   0   0

As a starting pattern, we will take #... This is because we can't place the first symbol before the start of the sequence. A sequence of one symbol, can only be written in one way, so the starting count-vector becomes 0 0 0 0 1 0 0 0.

The final pattern we want is #... No symbol beyond the end of the sequence, but the remaining must be filled. The pattern is that after the shift. This means we want to look at position 5 in the vector (counting from 1).

The first few values we get are:

n   p(n,1)
1        1
2        2
3        3
4        5
5        8
6       13
7       21
8       34

Of course, much of the matrix is redundant. You could spend some time to eliminate rows and columns. I won't demonstrate this.

Once we have a few values, we can try to find the recurrence relation. First let's try a system of size 1:

1·a = 2

This would solve to a = 2. But if we try the next value, we will see that if fails already on the next value:

2·a = 2·2 = 4 ≠ 3.

Next, lets try a system of size 2:

1·a + 2·b = 3
2·a + 3·b = 5

This solves to a = b = 1. This will actually generate the whole sequence.

3·a + 5·b = 3·1 + 5·1 = 8
5·a + 8·b = 5·1 + 8·1 = 13
...

If we try an even bigger system, we will run into problems:

1·a + 2·b + 3·c = 5
2·a + 3·b + 5·c = 8
3·a + 5·b + 8·c = 13

This solves to a = 1 - c, b = 2 - c, without any value for c.

If we try the sequence for K = 2 (generated with the above method): 1 2 6 14 31 73 172 400 932 2177

This won't give a valid solution until size 5: a = -1, b = 0, c = 2, d = 0, e = 2. This is the same relation as you found.