Carillon peals

A carillon rings all of its bells once, in some order. Two bells cast to the same pitch sound the same, so swapping them changes nothing a listener could hear.

The problem

The tower holds a fixed set of bells, each recorded by its pitch number. A peal uses every bell exactly once, in some order, and is identified by the sequence of pitches it sounds rather than by which physical bell rang.

Write out every peal the tower can ring, each one once. The peals may be listed in any order, but no two of them may sound the same.

Input. bells — a list of integers, the pitch of each bell in the tower. Pitches repeat when two bells were cast alike.

Output. A list of peals, each a list of pitches with the same length as bells, with no two peals identical.

Example.

bells = [3, 3, 7]   ->  [3,3,7], [3,7,3], [7,3,3]

Three peals, not six. The two bells at pitch 3 can be swapped in every one of the six orderings, and each swap leaves the sound unchanged.

A second example, where nothing is shared:

bells = [1, 2, 3]   ->  [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

With all pitches distinct, the count is the full 3! = 6. Going the other way, bells = [4, 4, 4] gives the single peal [4,4,4].

Constraints.

• 1 <= len(bells) <= 8
• 1 <= bells[i] <= 50
• Every bell must appear in every peal.

Hints

Approach

Brute force

Generate all n! orderings with a used-flag search and drop repeats with a set of tuples. Eight bells give 40,320 orderings; with six of them sharing a pitch, that is hundreds of copies of the same peal, nearly all discarded.

The insight

Sort the pitches, and refuse to ring a bell whose identical left-hand neighbour is still unused — equal bells are then always spent left to right, so each audible peal is built exactly once.

Every duplicate peal comes from permuting a group of equal pitches among themselves. Of the many index orders that produce one peal, exactly one spends each group left to right, and the rule keeps precisely that one. Sorting is the precondition: the check pitches[i] == pitches[i-1] and not used[i-1] only sees a group when equal values are adjacent.

Algorithm

1. Sort the pitches and create a used flag per index.
2. If the working peal is full, record a copy and return.
3. Loop over the indices. Skip index i if it is used.
4. Skip it also if pitches[i] == pitches[i-1] and index i-1 is unused.
5. Mark i used, append its pitch, recurse, then pop and unmark.

Complexity

Time O(n · P) where P is the number of distinct peals — the search never enters a branch that leads to a duplicate, and each finished peal costs n to copy. Space O(n) for the flags, the working peal and the recursion depth.

Solution

"""Carillon peals — distinct orderings of a multiset of bells, by backtracking."""


def solve(bells):
    pitches = sorted(bells)           # equal pitches adjacent, so the skip rule can see them
    used = [False] * len(pitches)
    peals, current = [], []

    def extend():
        if len(current) == len(pitches):
            peals.append(list(current))
            return
        for i, pitch in enumerate(pitches):
            if used[i]:
                continue
            # invariant: among equal pitches, only the leftmost unused one may be rung next,
            # so equal bells are always consumed left to right and no ordering repeats
            if i > 0 and pitch == pitches[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            current.append(pitch)
            extend()
            current.pop()
            used[i] = False           # the bell is free again for the next branch

    extend()
    return peals

TESTS = [
    (([3, 3, 7],), [[3, 3, 7], [3, 7, 3], [7, 3, 3]]),
    (([1, 2, 3],), [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]),
    (([4, 4, 4],), [[4, 4, 4]]),
    (([2, 2, 5, 5],), [[2, 2, 5, 5], [2, 5, 2, 5], [2, 5, 5, 2],
                       [5, 2, 2, 5], [5, 2, 5, 2], [5, 5, 2, 2]]),
    (([6],), [[6]]),
]

Pitfalls

• Skipping when used[i-1] is true rather than false keeps the mirror image of the intended rule. It still cuts duplicates, but it also drops valid peals when the group is split across positions.
• Not sorting first leaves equal pitches apart, so the neighbour test never matches and [3,3,7] comes out twice.
• Recording the working list instead of a copy leaves every peal in the output pointing at the same list, which ends up empty after the last undo.
• Forgetting to unmark used[i] after the recursive call loses whole branches, and for [1,2,3] you get one peal instead of six.

Variants

• Donation hampers — the same duplicate skip on selections, where the test is positional instead of flag-based.
• Bead kit bracelets — building a sequence slot by slot when the choices are independent and nothing is consumed.