progress

~/problems / Randomness / Randomized algorithms

Plant swap: nobody keeps their own cutting

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy ~15 min

At a plant-swap club, every member brings one cutting and takes one home, and nobody may take their own. Every valid assignment must be equally likely.

Write plant_swap(members: list[str], rng: random.Random) -> dict[str, str], mapping each member to whose cutting they take: every member appears once as a key and once as a value, and result[m] != m. For 4 members there are 9 valid assignments, each about 1/9 of the time. Use only rng for randomness.

plant_swap(["ana", "ben"], random.Random(0))          # {"ana": "ben", "ben": "ana"}  (the only option)
plant_swap(["ana", "ben", "cy"], random.Random(1))    # either ana->ben, ben->cy, cy->ana
                                                      # or     ana->cy, cy->ben, ben->ana, each half the time

Shortcuts that are not uniform: "shuffle, then pass each cutting one seat left" (always one big circle), and "shuffle, then patch fixed points by swapping with a neighbour".

2 <= len(members) <= 10^4, names distinct.

⭐ Bonus: a speed test drawing 40 swaps for 10,000 members earns a star at expected O(n) per call.

Show hint

draw a uniform permutation; if someone keeps their own, throw it away and draw again. Survivors stay equally likely, and over a third of permutations survive.

Topic: Randomized algorithms. Reservoir sampling, Fisher-Yates, rejection sampling.

0:00
Ctrl ' run · Ctrl ↵ submit
esc