0

以下のリンクをご覧ください。 文字列の順列: 繰り返される順列を削除するには?

これをactionscript 2に移植したいと思います。これまでのところ、次のとおりです。

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

これは、重複のあるすべての順列をリストするのにうまく機能していますが、それらを削除して一意の値を持ちたいと考えています。これまでのところ、上記のリンクからチェックされたソリューションを移植することができませんでした。ご協力ありがとうございました。

4

1 に答える 1

0

以下は2つのバージョンです。1つは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;
}

編集：

実は今考えてみると、どんな重複を避けようとしていたのかわかりません。上記のコードは、AACやACAなどのAACの順列を別個のものとして扱いますが（Aが「複製」されている場合でも）、AACとAACは同じと見なされます（最初のAと2番目のAが来る場合でも）元の配列のさまざまなソースから）。

生成された配列の重複した要素を削除したい場合は、明らかに、最初にソースからそれらを削除するのが最善の戦略です。

于 2012-05-02T12:17:10.300 に答える