使用回溯的独特排列

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] 

为什么我仍然有结果的重复？

Answer 1

那么你有你的输入数组中重复的元素。这可能会导致您的解决方案中的元素冗余或冗余排列，但是如果您在阵列中使用了输入（如独特元素），例如...

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] 

希望这可以帮助你:)

Answer 2

这是因为你正在开关到你的列表'就地'。 （即：您要修改您的清单，而计算排列）

这一个quickfix你的代码：

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 3

如果你想避免因重复号码重复，可以先排序您的数据，然后添加一个条件，使交换（仅当元素为大）：

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] 

Answer 4

在过滤中，您使用一对一检查。所以如此，但那不是工作从现在有三个以上元素。

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

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