derange

A CLI tool that generates a derangement of a list of names or items — a permutation where no element appears in its original position.

What is a derangement?

A derangement is a permutation of a set in which no element appears in its original position. For example, given [A, B, C], the arrangement [B, C, A] is a derangement because A is not first, B is not second, and C is not third.

Algorithm

derange uses Sattolo's algorithm to generate a uniformly random single-cycle permutation — a special kind of derangement where all elements form one continuous cycle. In a gift exchange this means the assignments form one unbroken chain: Alice gives to Bob, Bob gives to Charlie, and so on until the last person circles back to Alice.

Sattolo's algorithm is an O(n) variation of the Fisher-Yates shuffle. For each position i from n-1 down to 1, swap the element at i with a randomly chosen element at a position strictly less than i. That one change — excluding i from the candidate range — guarantees the single-cycle derangement property with no retries needed.

Installation

cargo install --path .

Usage

Provide a list of names, one per line, via a file or stdin:

# From a file
derange --input names.txt

# From stdin
echo -e "Alice\nBob\nCharlie\nDiana" | derange

# JSON output
derange --input names.txt --format json

Example: Gift Exchange

Create a file with participant names:

Alice
Bob
Charlie
Diana
Eve

Run derange:

$ derange --input names.txt
Alice => Charlie
Bob => Eve
Charlie => Diana
Diana => Alice
Eve => Bob

Each person gives a gift to the person on the right side of the arrow. No one buys a gift for themselves, and the single-cycle property ensures every participant is connected — no one is left out of the loop.

Other Uses

• Secret Santa / anonymous gifting — same principle as a gift exchange, but identities stay hidden until reveal day
• Peer review assignments — distribute code reviews or essays so no one evaluates their own work
• Lab partner or team shuffles — pair students or colleagues without anyone being matched with themselves
• Round-robin scheduling — assign opponents ensuring no team is slated against itself in a given round
• Secret buddy programs — anonymous pairing for mentorship, check-ins, or wellness initiatives
• Blind taste or quality tests — assign samples to evaluators so no one judges what they produced
• Data anonymization — shuffle dataset records so no row retains its original index
• Randomized seating — reseat attendees so no one returns to their original chair