バックトラックを使用した一意の順列

Question

私は一意のパーマネントを見つける問題でバックトラッキングを使用しようとしています。この例では、この1つは、私はまだ結果で重複しなければならないのはなぜ

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] 

動作しない

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

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

を作品

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) 

：私はこれを書かれていますか？

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

OUTPUTがある...助けるかもしれない

[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

これは、あなたのリストにスイッチを適用しているからです。 （すなわち：。順列を計算しながら、あなたはあなたのリストの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] 

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

順列が同じように見えます（ただし、2つの2つの原点は異なります）。そこで、2つのスワップを間接的に交換しました。

それでも、それを複雑にする必要はありません。ここで働くかもしれない二つのアプローチがあります。

• ソートリスト、およびあなたが以前よりも辞書的によりますリストをのみを発することができる制約を施行は、
• 最初にオカレンスをカウントします（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)]