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))