c codeをactionscriptに移植する2

Question

次のリンクをご覧ください。私はポート2.ここでのActionScriptのためにこれをしたいと思います Permutation of String letters: How to remove repeated permutations?

は私がこれまで持っているものです。

var str:String = "AAC"; 
var arr:Array = str.split(""); 

permute(0,2); 

function swap(i:Number, j:Number) 
{ 
    var temp; 
    temp = arr[i]; 
    arr[i] = arr[j]; 
    arr[j] = temp; 
} 

function permute(i:Number, n:Number) 
{ 
    var k:Number; 

    if (i == n) 
    trace(arr); 
    else 
    { 
     for (k = i; k <= n; k++) 
     { 
       swap(i, k); 
       permute(i+1, n); 
       swap(i, k);   
     } 
    } 
} 

これは、重複してすべての順列をリストアップして正常に動作しているが、私はそれらを削除したいと固有の値を持つこれまでのところ私は上のリンクから目を通した解決策を移植することはできませんでした。ご協力ありがとうございました。

Answer 1

次の2つのバージョンがあります。最初はAS3、2番目はAS2です。それはやや異なるアルゴリズムです（あなたが持っているアルゴリズムよりも効率が少し劣りますが、これはイラストレーションとして行うと思います）。基本的に同じアルゴリズムの複雑さなので、冗長性は中間結果（より短い配列）を生成することにあり、後で破棄されます（ただし、これが問題であればそれらの配列を再利用するように変更できます）。

AS3

private function permuteRecursively(input:Array, 
    hash:Object = null):Array 
{ 
    var first:String; 
    var oldResult:Array; 
    var newResult:Array; 
    var times:int; 
    var current:Array; 
    var test:String; 

    if (input.length > 1) 
    { 
     first = input.shift(); 
     if (!hash) hash = { }; 
     oldResult = this.permuteRecursively(input, hash); 
     newResult = []; 
     for each (var result:Array in oldResult) 
     { 
      times = result.length; 
      while (times >= 0) 
      { 
       current = result.concat(); 
       if (times == result.length) current.push(first); 
       else current.splice(times, 0, first); 
       test = current.join(""); 
       if (!(test in hash)) 
       { 
        newResult.push(current); 
        hash[test] = 1; 
       } 
       times--; 
      } 
     } 
    } 
    else newResult = [input]; 
    return newResult; 
} 

AS2：

private function permuteRecursively(input:Array, 
    hash:Object):Array 
{ 
    var first:String; 
    var oldResult:Array; 
    var newResult:Array; 
    var times:Number; 
    var current:Array; 
    var test:String; 
    var result:Array; 

    if (input.length > 1) 
    { 
     first = input.shift(); 
     if (!hash) hash = { }; 
     oldResult = this.permuteRecursively(input, hash); 
     newResult = []; 
     for (var i:Number = 0; i < oldResult.length; i++) 
     { 
      result = oldResult[i]; 
      times = result.length; 
      while (times >= 0) 
      { 
       current = result.concat(); 
       if (times == result.length) current.push(first); 
       else current.splice(times, 0, first); 
       test = current.join(""); 
       if (!(test in hash)) 
       { 
        newResult.push(current); 
        hash[test] = 1; 
       } 
       times--; 
      } 
     } 
    } 
    else newResult = [input]; 
    return newResult; 
} 

EDIT：実際

、今私はそれについて考えることを、私はあなたがしようとしていた重複のどのようなわからないんだけど避けるために。上記のコードは、AACやACAなどのAACの順列を、たとえAが「複製」されていても）区別できるように扱いますが、AACとAACは同じと見なされます（最初のAと2番目のAは元の配列の異なるソースから）。

生成された配列の複製された要素を削除したい場合、最初にソースから削除することをお勧めします。