Suppose there are three colored hangers—red, green, and blue—and three matching shirts. The shirts have been hung in the wrong places. What is the fewest number of swaps needed to put every shirt on its matching hanger?

It looks like a tiny sorting puzzle. Underneath, it is a clean demonstration of permutations, cycle decomposition, and optimal algorithms.

Interactive permutation

Match every shirt to its hanger

Randomize the shirts, inspect the cycles, and watch the optimal swaps.

Permutation
Cycles
Minimum swaps
Swaps performed0

Ready to solve.

Why the solution is optimal

Every arrangement of the shirts is a permutation. Draw an arrow from each hanger color to the color of the shirt currently beneath it. Those arrows split the permutation into cycles.

For example, the arrangement (Blue, Red, Green) creates one cycle:

Red→Blue→Green→Red

A cycle containing k shirts takes exactly k − 1 swaps to repair. More generally, each swap can increase the number of cycles by at most one. The solved arrangement has n one-item cycles, so an arrangement starting with c cycles requires at least n − c swaps. The algorithm reaches that lower bound:

minimum swapsn − number of cycles

With three shirts, the worst case is one three-item cycle, so the answer can never be more than two swaps.

The algorithm

The algorithm scans the hangers from left to right. Whenever a hanger has the wrong shirt, it finds the correct shirt and swaps it into place. That fixes one position without disturbing any position already fixed.

import random

COLORS = ["Red", "Green", "Blue"]

def random_assignment():
    shirts = COLORS.copy()
    random.shuffle(shirts)
    return shirts

def optimal_swaps(shirts):
    """
    shirts[i] is the shirt currently on hanger i.
    Hanger order is Red, Green, Blue.
    Returns a list of optimal swaps.
    """

    target = {color: i for i, color in enumerate(COLORS)}
    pos = {shirt: i for i, shirt in enumerate(shirts)}
    swaps = []

    for hanger in range(3):
        correct = COLORS[hanger]

        if shirts[hanger] == correct:
            continue

        current = pos[correct]
        swaps.append((hanger, current))

        shirts[hanger], shirts[current] = shirts[current], shirts[hanger]
        pos[shirts[current]] = current
        pos[shirts[hanger]] = hanger

    return swaps

For ['Blue', 'Red', 'Green'], the algorithm first swaps the red and green hanger positions, then swaps the remaining blue and green shirts. The result is ['Red', 'Green', 'Blue'] in two moves—the exact minimum predicted by the cycle formula.

What looks like a simple sorting demo is really a compact graph-theory problem. The picture makes the cycles intuitive; the proof guarantees optimality; and the algorithm turns that proof into a sequence of visible moves.

The real-closet version

Real closets do not have one shirt of each color. They contain repeated colors, and those colors are not evenly distributed. Research on clothing preferences found that black, white, and gray account for about 60% of selections, while sales data for men’s T-shirts also puts black and white first, followed by navy and dark gray. That suggests a heavily neutral closet with a long tail of other colors. (Clothing-color study, men’s T-shirt sales report)

The simulator below uses this modeled distribution:

Black 25% White 19% Gray 15% Navy 8% Blue 6% Brown/tan 6% Multicolor 5% Red 4% Green 3% Pink 2% Purple 2% Yellow 2% Orange 1% Teal 1% Other 1%

There is one important constraint: a perfect match is possible only when the hanger colors and shirt colors have the same counts. The generator therefore creates one matching hanger for every shirt, then randomly rearranges the pairs so no shirt starts on its matching color.

Duplicate-color assignment

Build an arbitrarily large closet

Items60
Matched0
Mismatched60
Swaps0
HangerShirtMatched pair

Every shirt begins on a different-colored hanger.

Matching repeated colors

With duplicate colors, individual black shirts are interchangeable; it does not matter which black shirt reaches a black hanger. The algorithm works from left to right:

  1. Leave every correctly matched position alone.
  2. At a mismatch, find a later shirt with the required color.
  3. Prefer a reciprocal swap that fixes both positions at once.
  4. Otherwise, make a swap that fixes the current position and continue.

This always finishes with every shirt matched and never disturbs an earlier position that has already been fixed. For a closet of n items, this straightforward implementation uses linear space for its working copy and returned swap list, and at most n − 1 swaps. Its search is quadratic in the worst case, which remains comfortable for the hundreds of items a real closet might contain.

def match_closet(hangers, shirts):
    """Return swaps that match duplicate-colored shirts and hangers."""
    if sorted(hangers) != sorted(shirts):
        raise ValueError("Hangers and shirts must have matching color counts")

    shirts = shirts.copy()
    swaps = []

    for i, required in enumerate(hangers):
        if shirts[i] == required:
            continue

        # Prefer a swap that fixes both mismatched positions.
        reciprocal = next((
            j for j in range(i + 1, len(shirts))
            if shirts[j] == required and hangers[j] == shirts[i]
        ), None)

        if reciprocal is not None:
            j = reciprocal
        else:
            j = next(
                j for j in range(i + 1, len(shirts))
                if shirts[j] == required and shirts[j] != hangers[j]
            )

        shirts[i], shirts[j] = shirts[j], shirts[i]
        swaps.append((i, j))

    return swaps

The original three-shirt puzzle is a permutation of distinct objects. This version is a many-to-one color assignment: there may be dozens of equivalent correct answers because shirts of the same color can trade identities without changing the closet.