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

下面是两个版本，第一个是针对 AS3 的，第二个是针对 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 的排列（例如 AAC 和 ACA来自原始数组中的不同来源）。

如果您想删除生成数组的重复元素，那么显然，最好的策略是首先从源中删除它们。

于 2012-05-02T12:17:10.300 回答