Generate unique permutations from a multiset using backtracking and in lexicographic order

Question

If there are duplicates (meaning our set is a multi-set), you can save considerable time and effort by avoiding identical permutations. For example, there are only ten distinct permutations of {1,1,2,2,2}, instead of 120.

The challenge is to avoid duplicates by using backtracking and generating the permutations in lexicographic order.

Here is what I have tried so far but it's inefficient because I am still enumerating repeat elements. I am also sorting the input first.

def multiset_permutation(A):

    def solve_permutation(k, seen):
        # goal
        if k == len(A) - 1 and tuple(A) not in seen:
            seen.add(tuple(A))
            result.append(A.copy())

        for i in range(k, len(A)):
            # make choice: swap elements
            A[k], A[i] = A[i], A[k]
            # explore: Generate all permutations for A[i + 1:]
            solve_permutation(k + 1, seen)
            # backtrack: undo choice
            A[k], A[i] = A[i], A[k]

    result = list()
    seen = set()

    solve_permutation(0, seen)

    return result

>>> multiset_permutation(sorted(A))
    [1, 1, 2], [1, 2, 1], [2, 1, 1]

What I am looking for is a way to break off the enumeration at the earliest chance. For example, given A=[1,1,2], the recursion tree would look like so with enumeration stopping at break-off points:

                                   []
                 /                 |                        \

       [1]               [1](break off - already enumerated)           [2]
      /    \                  /     \                                /     \
    [1,1] [1,2]           [1,1]    [1,2]                         [2,1]   [2,1] (break off - already enumerated)
       /      \              /       \                               /      \

[1, 1, 2]   [1, 2, 1]     [1, 1, 2]   [1, 2, 1]                  [2, 1, 1]   [2, 1, 1]

Expected output:

[1, 1, 2], [1, 2, 1], [2, 1, 1]

[This answer](https://stackoverflow.com/a/6285203/13253198) looks like exactly what you are looking for. But I don't know its performance. Trivially you can use `itertools` and `set`, but that doesn't use backtracking to avoid duplicates. — gnodab, May 22 '20 at 14:46
I used a `Counter` object to emit based on counters of each element and that helped with avoiding enumerating repeat elements, [implementation](https://stackoverflow.com/a/61997672/7695722). — Brayoni, May 25 '20 at 07:40

Brayoni · Answer 1 · 2020-05-25T07:38:48.740

In the following approach, we avoid enumerating repeat elements but we still sort our data to emit permutations in lexicographic order.

def multiset_permutation(A):

    def solve_permutation(depth, counter, permutation):
        # base case/goal
        if depth == 0:
            yield permutation
            return

        # choices
        for key, value in counter.items():
            # constraint
            if value > 0:
                # make a choice
                counter[key] -= 1
                permutation.append(key)

                # explore
                yield from [
                    list(i) for i in solve_permutation(depth - 1, counter, permutation)
                ]

                # backtrack - undo our choices
                permutation.pop()
                counter[key] += 1

    """
    Lexicographical order requires that we sort the list first so that we
    incrementally emit the next larger permutation based on the counters
    """
    A = sorted(A)
    counter = collections.Counter(A)

    return list(solve_permutation(len(A), counter, []))

Output:

[[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Call Stack to solve [1, 1, 2] will looks as follows:

depth counter permutation
0, {1:0, 2:0}, [1,1,2]
1, {1:0, 2:1}, [1,1]
2, {1:1, 2:1}, [1]
3, {1:2, 2:1}, []

0, {1:0, 2:0}, [1,2,1]
1, {1:0, 2:1}, [1,2]
2, {1:1, 2:1}, [1]

0, {1:0, 2:0}, [2,1,1]
1, {1:0, 2:1}, [2,1]
2, {1:1, 2:1}, [2]
3, {1:2, 2:1}, []

Recursive Tree:

                 []
           /           \

        [1]                  [2]
      /    \                  |        
    [1,1]  [1,2]             [2,1]   
    /         \               |      

[1, 1, 2]   [1, 2, 1]      [2, 1, 1]

Generate unique permutations from a multiset using backtracking and in lexicographic order

1 Answers1