The shuffle's code
A card game server shuffles a deck of n cards with the Fisher–Yates algorithm. The cards lie in places 1, 2, …, n, with card k in place k at first. Then for i = n, n − 1, …, 2 the generator produces a number ji from 1 to i, and the cards in places i and ji are swapped (if ji = i, nothing happens).
An auditor wants to check the generator, but the server log records only the order of the deck after shuffling. Recover the numbers the generator produced. They are determined by the deck uniquely, and the fairness of the algorithm rests on this.
Input
The first line holds n (1 ≤ n ≤ 105). The second holds n distinct numbers from 1 to n: which card ended up in place 1, in place 2, and so on.
Output
On one line, separated by spaces, n − 1 numbers: jn, jn−1, …, j2. For n = 1, an empty line.
Examples
Example 1
5 3 5 1 4 2
2 4 1 2
Example 2
4 1 2 3 4
4 3 2
Limits
- Time · Python
- 3000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 12 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Which places change after step i? What can be said about the card in place i in the final deck?
2Hint 2
Step i puts into place i the card that lay in place ji. So ji is where the needed card lay before step i. But by then the cards have already been moved by earlier steps.
3The idea
After step i place i is no longer touched: the following steps change only places with smaller numbers. So the final card in place i is the one that got there at step i. Repeat the shuffle from a sorted deck and at each step find where the card that must end up in place i lies now: its place is ji. To search instantly, keep an inverse array “card → place” and update it at every swap.
4Walkthrough
In the first example the final deck is 3 5 1 4 2. Step 5: card 2 must go into place 5, it lies in place 2, so j5 = 2; swap, and the deck is 1 5 3 4 2. Step 4: card 4 is in place 4, j4 = 4, nothing changes. Step 3: card 1 is in place 1, j3 = 1; the deck is 3 5 1 4 2. Step 2: card 5 is in place 2, j2 = 2. The answer: 2 4 1 2.
The solution proves that the numbers are determined by the deck uniquely: each ji is computed, not guessed. Conversely, any numbers with 1 ≤ ji ≤ i give some deck. So there are as many sets of numbers as decks, n·(n − 1)·…·2 = n!, with a one-to-one correspondence between them. If the generator produces all sets with equal probability, all n! decks are equally likely too: this is the proof of Fisher–Yates’s fairness from the article. Such a record of a permutation as a set of numbers is known as the factorial number system: ji − 1 is a “digit” with base i.
4+Solution
5Complexity
O(n) time and memory: one swap and one access to the inverse array per step.
6Common mistakes
- Taking the card’s original place. Card c starts in place c, but earlier steps have already moved it. The answer “the final card in place i” is wrong already on the first example.
- Searching for the card by scanning.
deck.index(card)at every step is O(n2), billions of comparisons on a hundred thousand cards. An inverse array is needed. - Forgetting to update the inverse array. After a swap the places of two cards change, and both must be recorded.