使用回溯的獨特排列

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