At a plant-swap club, every member brings one cutting and goes home with exactly one cutting, and nobody may go home with their own. The organiser wants the assignment to be fair: every valid assignment should be equally likely.
Write plant_swap(members: list[str], rng: random.Random) -> dict[str, str] mapping each member to the member whose cutting they take home.
- Every member appears exactly once as a key and exactly once as a value, and
result[m] != mfor everym. - Each valid assignment must have the same probability. For 4 members there are 9 valid assignments, so each should come up about 1/9 of the time.
- Use only
rngfor randomness (rng.shuffle,rng.randrange, ...), never the globalrandommodule.
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
Tempting shortcuts are not uniform: "shuffle, then pass each cutting one seat to the left" only ever makes one big circle (for 4 members it can't produce ana<->ben, cy<->dee), and "shuffle, then patch any fixed point by swapping with a neighbour" favours some assignments.
Constraints: 2 <= len(members) <= 10^4, names are distinct. The tests call it many times on large lists, so aim for expected O(n) time per call.
Show hint
A uniformly random permutation is easy to draw. If you simply discard the ones where someone keeps their own cutting and draw again, every surviving assignment stays equally likely, and more than a third of permutations survive, so few retries are needed.