Introduction

The letters-and-envelopes problem usually means pairing n letters with n envelopes so that no letter goes into its own envelope. In combinatorics that is a derangement. The algorithmic part is deciding whether you need to count all valid pairings or construct one efficiently.

Understanding the Constraint

If letter i normally belongs to envelope i, then a valid pairing is a permutation with no fixed points. For n = 4, this is valid:

• '0 -> 1'
• '1 -> 2'
• '2 -> 3'
• '3 -> 0'

Each letter moves to a different envelope, and none stays in its original position.

Two separate tasks often get mixed together:

1. count the number of valid pairings
2. generate one valid pairing

The first is a counting problem. The second is a construction problem.

Counting Valid Pairings

The number of derangements of n items is written as !n. A practical recurrence is:

!n = (n - 1) * (!(n - 1) + !(n - 2))

with base cases:

• '!0 = 1'
• '!1 = 0'

Here is a dynamic-programming implementation:

1def count_derangements(n: int) -> int:
2    if n == 0:
3        return 1
4    if n == 1:
5        return 0
6
7    dp = [0] * (n + 1)
8    dp[0] = 1
9    dp[1] = 0
10
11    for i in range(2, n + 1):
12        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])
13
14    return dp[n]
15
16
17for n in range(6):
18    print(n, count_derangements(n))

This runs in O(n) time and is the right choice when you only need the count.

Constructing One Pairing

If the goal is simply to build one correct assignment, the easiest deterministic algorithm is a cyclic shift:

1def pair_letters_with_envelopes(n: int) -> list[tuple[int, int]]:
2    if n < 2:
3        raise ValueError("A derangement requires at least 2 items.")
4
5    return [(i, (i + 1) % n) for i in range(n)]
6
7
8print(pair_letters_with_envelopes(5))

This works for every n >= 2. Letter 0 goes to envelope 1, letter 1 goes to envelope 2, and the last letter wraps around to envelope 0.

That solution is linear, obvious, and easy to verify. If you do not need randomness, it is hard to beat.

Constructing a Random Pairing

Sometimes you want a random valid pairing. A simple method is to shuffle until no item stays in place:

1import random
2
3
4def random_derangement(n: int) -> list[int]:
5    if n < 2:
6        raise ValueError("A derangement requires at least 2 items.")
7
8    items = list(range(n))
9    while True:
10        random.shuffle(items)
11        if all(i != items[i] for i in range(n)):
12            return items[:]
13
14
15print(random_derangement(6))

This is easy to implement and is usually fine for modest input sizes. The tradeoff is that it may retry several times before it finds a valid derangement.

If you need strict performance guarantees, use a constructive algorithm instead of repeated shuffling.

Verifying the Result

Whether you generate the pairing deterministically or randomly, validation is straightforward:

1def is_valid_pairing(mapping: list[int]) -> bool:
2    n = len(mapping)
3    return sorted(mapping) == list(range(n)) and all(i != mapping[i] for i in range(n))
4
5
6mapping = random_derangement(5)
7print(mapping, is_valid_pairing(mapping))

This check confirms both requirements:

• the mapping is a permutation
• there are no fixed points

That is exactly what the problem demands.

Common Pitfalls

The biggest pitfall is forgetting the edge case n = 1. There is no valid pairing because the only letter would have to go into its own envelope.

Another mistake is solving the counting problem when the real requirement is only to construct one valid mapping. The recurrence is interesting, but it does not directly produce the pairing.

People also assume a random shuffle is automatically valid. It is not. A shuffled permutation still needs fixed-point checking.

Finally, do not overengineer the construction step. If you only need one correct answer, a simple cyclic shift is usually the cleanest algorithm.

Summary

• The letters-and-envelopes pairing problem is the derangement problem.
• Counting valid pairings uses the recurrence for !n.
• Constructing one valid pairing is easy with a cyclic shift.
• Random valid pairings can be generated by shuffle-and-check for moderate sizes.
• Always verify that the result is a permutation with no fixed points.