使用回溯法并按词法顺序从一个多组中生成唯一的排列组合。

Question

如果有重复的情况（意味着我们的集合是一个多集合），你可以通过避免相同的排列组合来节省大量的时间和精力。例如，{1,1,2,2,2}只有10种不同的排列组合，而不是120种。

我们面临的挑战是如何通过使用回溯和按词法顺序生成排列组合来避免重复。

这是我目前尝试过的方法，但效率很低，因为我仍然在枚举重复元素。我也是先对输入进行排序。

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] 

我正在寻找的是一种在最早的机会中断枚举的方法。例如，给定 A=[1,1,2]递归树看起来像这样，枚举在断点处停止。

                                   []
                 /                 |                        \

       [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]

预期的输出。

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

Answer 1

在下面的方法中，我们避免枚举重复元素，但我们仍然按照词法顺序对数据进行排序，以发出排列组合。

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, []))

输出。

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

调用Stack来解决 [1, 1, 2] 将看起来如下。

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}, []

递归树：

                 []
           /           \

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

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