Random shuffle#1584

Random shuffle (Editorial)

Initially, we have the array ${1, 2, ..., n}$ \{1, 2, ..., n\}. Then a shuffling procedure is performed. We are given the final permutation $A$ . We need to find the probability that this exact permutation is obtained after the procedure.

The required probability is equal to:

\frac{n u mb er o f w a y s t o o b t ain А}{t o t a l n u mb er o f p oss ib l e s h u f f l es}

\frac{number~of~ways~to~obtain~А}{total~number~of~possible~shuffles}

At each step of the shuffle, a number $r$ is chosen. There are $n$ possible choices for $r$ . The number of shuffling steps is also $n$ . Therefore, there are $n^{n}$ n^n possible sequences of choices. Note that different sequences of choices may lead to the same final permutation, because $n^{n}$ n^n is much larger than $n!$ .

Let us store the sequence ${1, 2, ..., n}$ \{1, 2, ..., n\} in the array $c u r$ . We'll iterate over all possible choices $(r_{1}, r_{2}, ..., r_{n})$ (r_1, r_2, ..., r_n), simulating in $c u r$ every possible shuffling process $(1 \leq r_{i} \leq n)$ (1 \le r_i \le n). Note that a fixed sequence of numbers $r_{1}, r_{2}, ..., r_{n}$ r_1, r_2, ..., r_n uniquely determines which swaps are performed at each step, and therefore also determines the final array after the procedure is completed. If, after applying all swaps, we obtain the array $A$ , we count the attempt as successful. Let the number of such successful attempts be $s$ . Then the required probability is equal to

s / n^{n}

s / n^n

Let's implement the shuffle function, which recursively enumerates all possible continuations of the shuffling process and counts how many of them lead to the target permutation $А$ .

The function has one parameter $p os$ , the index of the current iteration (starting from $0$ ). This means that the first $p os$ swaps have already been performed, and the array $c u r$ stores the state obtained after these operations.

To fit within the time limit, apply the following pruning. Suppose we are at iteration $p os$ , and the current array $c u r$ differs from the target array $A$ in $d i f f$ positions. There are $n - p os$ n - pos swaps left to perform. Note that a single swap can place at most two elements into their correct positions. Therefore, over the remaining steps we can fix no more than $2 \cdot (n - p os)$ 2 \cdot (n - pos) positions in total.

If $d i f f > 2 \cdot (n - p os)$ diff > 2 \cdot (n - pos), then it is already impossible to transform $c u r$ into $A$ . In this case, continuing the search makes no sense, and the current branch of the recursion can be terminated immediately.

Algorithm implementation

Let us declare the following arrays:

$a$ — the given permutation $А$ ;
$c u r$ — the current permutation during the enumeration;

int a[10], cur[10];

The shuffle function recursively enumerates all possible continuations of the shuffling process, counting how many of them lead to the target permutation $A$ .

void shuffle(int pos) 
{

After all $n$ operations have been performed, it remains to check whether the obtained array $c u r$ matches the required permutation $A$ . If it does, then we have found another successful scenario. In this case, increment $co u n tG oo d$ .

  if (pos == n) 
  {
    for (int i = 0; i < n; i++)
      if (cur[i] != a[i]) return;
    countGood++;
    return;
  }

C++

In the variable $d i f f$ , count the number of positions where the current array $c u r$ differs from the required permutation $A$ .

  int diff = 0;
  for (int i = 0; i < n; i++)
    if (cur[i] != a[i]) diff++;

At this point, we still have $n - p os$ n - pos steps left to perform. A single swap can fix at most two incorrect positions. If the number of differences already exceeds what can possibly be fixed, then continuing the recursion is pointless.

So we simply stop exploring this branch of the search.

  if (diff > 2 * (n - pos)) return;

Iterate over all possible values of $r$ .

  for (int r = 0; r < n; r++) 
  {
    swap(cur[pos], cur[r]);
    shuffle(pos + 1);
    swap(cur[pos], cur[r]);
  }
}

C++

The main part of the program. Read the number $n$ — the size of array $А$ .

while (scanf("%d", &n) == 1)
{

Read the input array $А$ . The simulation always starts with the array ${1, 2, ..., n}$ \{1, 2, ..., n\}, which we store in $c u r$ .

  for (int i = 0; i < n; i++)
  {
    scanf("%d", &a[i]);
    cur[i] = i + 1;
  }

Start the enumeration. The variable $co u n tG oo d$ counts how many sequences of random choices lead to the array $A$ .

  countGood = 0;
  shuffle(0);

Compute and print the result.

  res = countGood / pow(n, n);
  printf("%.6lf\n", res);
}