NumPy: A Fisher–Yates shuffle

rng.permutation shuffles with the Fisher–Yates method. Given the random draws it would make, carry out the shuffle.

What to build

A program that shuffles items using given random positions.

Requirements

  • For i from the last position down to 1, take the next draw j (0 ≤ j ≤ i) and swap the items at positions i and j.
  • Print the shuffled items separated by spaces.

Input

Line 1: the items, words separated by spaces. Line 2: the n − 1 draws, in the order they are used.

Output

One line.

Constraints

2 to 1000 items; each draw is between 0 and the current i.

Example

Input:

a b c d
1 0 1

Output:

c d a b

Why it works

At each step the item placed at position i is chosen uniformly from the items not yet placed, so with truly random draws every order is equally likely.

Examples

Example 1 · Input
a b c d
1 0 1
Expected output
c d a b
Example 2 · Input
1 2
0
Expected output
2 1

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Loop i from len(items) − 1 down to 1, taking the next draw as j each time.

Hint 2

Swap with items[i], items[j] = items[j], items[i].

Solution

Show one correct solution (try it yourself first)
items = input().split()
draws = [int(x) for x in input().split()]
k = 0
for i in range(len(items) - 1, 0, -1):
    j = draws[k]
    k += 1
    items[i], items[j] = items[j], items[i]
print(" ".join(items))

Lesson: Random numbers and simulation →