バックトラックを使用したPythonの置換

Question

バックトラックを使用して順列を学習しようとしています。私は次のコードを書いたが、最初の出力の後に停止する。

def permutations(str_in, soFar): 

    if len(str_in) != 0: 
     for c in str_in: 
      soFar.append(c) 
      temp_str = str_in 
      temp_str.remove(c) 
      print temp_str, soFar 
      permutations(temp_str, soFar) 
    else: 
     print soFar 

inp = "ABCD"   
str_in = list(inp) 
permutations(str_in, []) 

これは私がこれを取得しています出力されます：

['B', 'C', 'D'] ['A'] 
['C', 'D'] ['A', 'B'] 
['D'] ['A', 'B', 'C'] 
[] ['A', 'B', 'C', 'D'] 
['A', 'B', 'C', 'D'] 

私は、これは単純なものであると確信しているが、私はここで作っているものを誤って理解することができませんよ。

Answer 1

ここでは、文字列を置換するBhavya JainのGeeksforgeeksメソッドがあります。あなたのコードに欠けているロジックは、サブリストの再帰的なステップとスワッピングの振る舞いです。ここに彼らの視覚化があります。

def permute(a, l, r): 
    if l==r: 
     print toString(a) 
    else: 
     for i in xrange(l,r+1): 
      a[l], a[i] = a[i], a[l] 
      permute(a, l+1, r) 
      a[l], a[i] = a[i], a[l] # backtrack 

# Driver program to test the above function 
string = "ABC" 
n = len(string) 
a = list(string) 
permute(a, 0, n-1) 

出力

['A', 'B', 'C'] 
['A', 'C', 'B'] 
['B', 'A', 'C'] 
['B', 'C', 'A'] 
['C', 'B', 'A'] 
['C', 'A', 'B'] 

Answer 2

私は再びそれを書き直したと私の間でいくつかの印刷コマンドで所望の出力に到達することができました。しかし、まだそれが働いている方法の完全なものではない。私は主に、pythonが関数呼び出しのたびにリストを変更する方法だと思います。元のリストを元に戻すことが変更されていないことを確認するために、一時的なリストを2回割り当てなければならなかった。とにかく、次のコードが動作しています。

def permute(String, SoFar): 
    TempString = list(String) 
    TempSoFar = list(SoFar) 
    #print TempString, TempSoFar 
    if TempString != []: 
     for c in String: 
      TStr = list(TempString) 
      TSF = list(TempSoFar) 
      TStr.remove(c) 
      TSF.append(c) 
      #print String, TStr, TSF 
      permute(TStr, TSF) 
    else: 
     print "\nOut: ", TempSoFar, "\n" 

permute(list("ABCD"),list("")) 

リストの代わりに文字列を使用する第2の解決策は、下記の私のコメントに記載されています。

def permute(String, SoFar): 
    #print "New Func Call: ", "SoFar: ", SoFar,"String: ", String, "\n" 
    if String != "": 
     for c in String: 
      TS = String.replace(c,"") 
      TSF = SoFar+c 
      permute(TS, TSF) 
      #print "A Call Finished", "SoFar: ", SoFar,"String: ", String, "TSF: ", TSF, "TS: ", TS 
    else: 
     print SoFar 

permute("ABC","")