Every distinct order when songs repeat

Sort the ids, then build orderings as usual with used flags, but skip a song when it equals the previous id and that previous copy is not in use. This makes equal copies always appear in the same relative order, so each distinct ordering is built once. O(n · n!) worst case, much less with many repeats. Apart from the output, it uses O(n) space.

The skip rule is the general 'no duplicate branches' trick for sorted input.

Building all orderings and putting them in a set works, but wastes work and memory.

A count map (value → copies left) is an equally clean alternative.

The mirror rule, skipping when the previous copy is in use, also builds each ordering once; it just prunes later.

def distinct_orders(songs: list[int]) -> list[list[int]]:
    items = sorted(songs)
    used = [False] * len(items)
    path: list[int] = []
    out: list[list[int]] = []

    def place() -> None:
        if len(path) == len(items):
            out.append(path[:])
            return
        for i, s in enumerate(items):
            if used[i]:
                continue
            if i and s == items[i - 1] and not used[i - 1]:
                continue  # equal copies are used left to right
            used[i] = True
            path.append(s)
            place()
            path.pop()
            used[i] = False

    place()
    return out

Common mistakes

• Checking only s == items[i - 1] and dropping not used[i - 1]: the second copy can then never be placed, so [1, 1, 2] gives no orderings at all.
• Forgetting to sort first, so equal values are not adjacent: [1, 2, 1] then yields each of its 3 orderings twice.

State the skip rule in words: 'equal copies are used left to right'.

Follow-up questions

Think of your answer first, then open the hint.

1. How many distinct orders does [1, 1, 2] have?

   Show hint

   3: 3! / 2!.

2. How does the count-map version work?

   Show hint

   At each slot, try each distinct value with copies left, decrement, recurse, increment.