使用回溯法生成唯一排列

Question

我正在尝试在寻找唯一排列问题中使用回溯算法。我已经写了以下代码：

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 = [2, 3, 2]
f(A, 0, len(A))

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

这个不起作用

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]

为什么我在结果中仍然有重复项？

- usual me

---

好的，你有A = [2,2,1,1]，在函数f中，你还将调用f([2,1,2,1], 1, len(A))，两种情况都可以输出[2,2,1,1]（第一种情况没有排列，第二种情况将索引1和2之间的元素进行排列）。 - Nuageux

Answer 1

在过滤过程中，您使用一对一检查。因此，但从那时起，当存在三个以上的元素时，这将无法运作。

这是因为您可以在多次（真实）交换之后获得相同的排列。例如：

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

正如您所看到的，排列是相同的（但两个“二”的起源不同）。 因此，我们间接交换了这两个“二”。

尽管如此，没有必要使它那么复杂。 这里有两种方法可能会起作用：

- 对列表进行排序，并强制执行一个约束条件，即您只能发出字典顺序更高的先前列表; 和 - 首先计算出现次数（使用Counter），然后确保您基于计数器发出。

后者将运行得更快，因为它不会生成必须省略的排列。

一个示例实现可能是：

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

这将给出：

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

- Willem Van Onsem

Answer 2

Willem的答案稍有变化，利用了yield from并解释了发生的事情。我们避免枚举重复元素，但仍然对数据进行排序以按字典顺序发出排列组合。

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

使用调用栈对解决 [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]

- Brayoni

Answer 3

你的输入数组中有重复元素。这可能会导致元素冗余或解决方案中的冗余排列，但如果你在数组中使用唯一元素，如...

A = [1,2,3,4...]，那么以下代码可能会有所帮助：

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

而这个的例子是...

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

输出结果为...

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

希望这能对你有所帮助 :)

- Kunal

---

你的输入数组中有重复元素 - 这是期望的，它是一个多重集合。 - Brayoni

Answer 4

这是因为您正在对列表“就地”应用开关。（即：在计算排列时修改了列表 A。）

这是您代码的快速修复：

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]

- Morreski

Answer 5

如果您想避免由于重复数字而产生的重复，可以先对数据进行排序，然后添加一个条件来进行交换（仅当元素较大时）。

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))

输出：

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

- Nuageux