Unique permutations using backtracking

Question

I am trying to use backtracking in the problem of finding unique permutions. I have written this:

def f(A, start, end):
    if start == end - 1:
        print(A)
    else:
        for idx in range(start, end):
            if idx != start and A[idx] == A[start]:
                continue
            A[idx], A[start] = A[start], A[idx]
            f(A, start + 1, end)

This example works

A = [2, 3, 2]
f(A, 0, len(A))

[2, 3, 2]
[2, 2, 3]
[3, 2, 2]

This one doesn't work

A = [2, 2, 1, 1]
f(A, 0, len(A))

[2, 2, 1, 1]
[2, 1, 2, 1]
[2, 1, 1, 2]
[2, 2, 1, 1] #unwanted duplicate!
[1, 2, 2, 1]
[1, 2, 1, 2]
[1, 1, 2, 2]
[1, 2, 2, 1]
[1, 2, 1, 2]
[2, 2, 1, 1]
[2, 1, 2, 1]
[2, 1, 1, 2]
[2, 2, 1, 1]

Why do I still have duplicates in the result?

Answer 1

In the filtering, you use a one-versus-one check. So as a result, but that will not work from the moment there are more than three elements.

This is because, you can obtain the same permutation after several (real) swaps. For example:

[1   ,2(1),2(2),3   ] -> swap 1 with 3
[1   ,3,   2(2),2(1)] -> swap 1 with 2
[1   ,2(2),3   ,2(1)] -> swap 2 with 3
[1   ,2(2),2(1),3   ]

As you can see the permutation is the same (but the origin of the two twos is different). So we swapped the two twos indirectly.

Nevertheless, there is no need to make it that complicated. There are two approaches that might work here:

• sort the list, and enforce a constraint that you can only emit lists that are lexicographically more than the previous; and
• first count the occurrences (using a Counter, then make sure you emit based on the counters).

The latter will run faster since it will not generate permutations it has to omit.

An example implementation could be:

from collections import Counter

def f(lst):
    def g(l,c,n):
        if n <= 0:
            yield tuple(l)
        else:
            for k,v in c.items():
                if v > 0:
                    c[k] -= 1
                    l.append(k)
                    for cfg in g(l,c,n-1):
                        yield cfg
                    l.pop()
                    c[k] += 1
    for cfg in g([],Counter(lst),len(lst)):
        yield cfg

This gives:

>>> list(f([1,1,2,2]))
[(1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 2, 1, 1)]
>>> list(f([1,1,2,2,3]))
[(1, 1, 2, 2, 3), (1, 1, 2, 3, 2), (1, 1, 3, 2, 2), (1, 2, 1, 2, 3), (1, 2, 1, 3, 2), (1, 2, 2, 1, 3), (1, 2, 2, 3, 1), (1, 2, 3, 1, 2), (1, 2, 3, 2, 1), (1, 3, 1, 2, 2), (1, 3, 2, 1, 2), (1, 3, 2, 2, 1), (2, 1, 1, 2, 3), (2, 1, 1, 3, 2), (2, 1, 2, 1, 3), (2, 1, 2, 3, 1), (2, 1, 3, 1, 2), (2, 1, 3, 2, 1), (2, 2, 1, 1, 3), (2, 2, 1, 3, 1), (2, 2, 3, 1, 1), (2, 3, 1, 1, 2), (2, 3, 1, 2, 1), (2, 3, 2, 1, 1), (3, 1, 1, 2, 2), (3, 1, 2, 1, 2), (3, 1, 2, 2, 1), (3, 2, 1, 1, 2), (3, 2, 1, 2, 1), (3, 2, 2, 1, 1)]

Answer 2

Well you have duplicate elements in your input array. This might lead to redundancy of elements or redundant permutations in your solution but if you used an input such as unique elements in your array such as...

A = [1,2,3,4...] and so on then following code might help

def f(A, start, end):
if start == end - 1:
    print(A)
else:
    for idx in range(start, end):
        if idx != start and A[idx] == A[start]:
            continue
        A[idx], A[start] = A[start], A[idx]
        f(A, start + 1, end)
        A[idx], A[start] = A[start], A[idx]  #This is added

And the example for this...

A = [1, 2, 3, 4]
f(A, 0, len(A))

The OUTPUT is...

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 3, 2]
[1, 4, 2, 3]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[2, 4, 1, 3]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 2, 3, 1]
[4, 2, 1, 3]
[4, 3, 2, 1]
[4, 3, 1, 2]
[4, 1, 3, 2]
[4, 1, 2, 3]

Hope this helps you :)

Answer 3

This is because you are applying switches to your list 'in place'. (i.e: you are modifying your list A while computing permutations.)

This is a quickfix to your code:

def f(A, start, end):
     if start == end - 1:
         print(A)
     else:
         B = A.copy()
         for idx in range(start, end):
             if idx != start and B[idx] == B[start]:
                 continue
             B[idx], B[start] = A[start], A[idx]
             f(B, start + 1, end)

A = [2, 2, 1, 1]
f(A, 0, len(A))
# [2, 2, 1, 1]
# [2, 1, 2, 1]
# [2, 1, 1, 2]
# [1, 2, 2, 1]
# [1, 2, 1, 2]
# [1, 1, 2, 2]

Answer 4

If you want to avoid duplicates due to repetitive numbers, you can first sort your data, then add a condition to make the exchange (only if element is larger):

def f_s(A, start, end):
    f(sorted(A), start, end)

def f(A, start, end):
    if start == end - 1:
        print(A)
    else:
        for idx in range(start, end):
            if idx != start and A[idx] == A[start]:
                continue
            if A[idx] >= A[start]:
                A[idx], A[start] = A[start], A[idx]
                f(A, start + 1, end)

A = [2, 3, 2]
f_s(A, 0, len(A))

A = [2, 2, 1, 1]
f_s(A, 0, len(A))

Output:

[2, 2, 3]
[2, 3, 2]
[3, 2, 2]

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

Answer 5

Slight variation of Willem's answer that leverages yield from and an explanation of what's happening. 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]