How to get an array all permutation in Actionscript 3.0?

Question

Suppose I have an array A = [0,1,2]. How do I get the 2 dimensional array perm_A = [[0,1,2],[0,2,1][1,0,2][1,2,0][2,1,0],[2,0,1]? The order of which the permutation appper in perm_A does not matter.

I used the code in Heap's Algoritm.

function generatePermute(k:int, arr:Array){
        if (k == 1){
        perm_list.push(arr);
    }
    else {
        generatePermute(k-1,arr);
    }
    for (var i = 0; i < k-1; i++){
        if (k % 2 == 0){
            swap_arr(arr, i, k-1);
        }
        else{
            swap_arr(arr, 0, k-1);
        }
        generatePermute(k-1,arr);
    }
}

function swap_arr(input, index_A, index_B) {
    var temp = input[index_A];
 
    input[index_A] = input[index_B];
    input[index_B] = temp;
}

var arr:Array = [0,1,2, 3]
var perm_list:Array = new Array();
generatePermute(4,arr);
for (var i = 0; i<perm_list.length;i++){
    trace(perm_list[i])
}

The result is :

1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0
1,2,3,0

which is clearly wrong.

update

if I change perm_list.push(arr); to trace (arr), I do get correct result. However, this only ouputs all the permutations in the console. I want to collect all of these permutations into a 2 dimensional array.

function generatePermute(k:int, arr:Array){
    if (k == 1){
        trace(arr)
    }
    else {
        generatePermute(k-1,arr);
    }
    for (var i = 0; i < k-1; i++){
        if (k % 2 == 0){
            swap_arr(arr, i, k-1);
        }
        else{
            swap_arr(arr, 0, k-1);
        }
        generatePermute(k-1,arr);
    }
}

function swap_arr(input, index_A, index_B) {
    var temp = input[index_A];
 
    input[index_A] = input[index_B];
    input[index_B] = temp;
}

var arr:Array = [0,1,2, 3]
var perm_list:Array = new Array();
generatePermute(4,arr);

which outputs

0,1,2,3
1,0,2,3
2,0,1,3
0,2,1,3
1,2,0,3
2,1,0,3
3,1,0,2
1,3,0,2
0,3,1,2
3,0,1,2
1,0,3,2
0,1,3,2
0,2,3,1
2,0,3,1
3,0,2,1
0,3,2,1
2,3,0,1
3,2,0,1
3,2,1,0
2,3,1,0
1,3,2,0
3,1,2,0
2,1,3,0
1,2,3,0

My guess is it seems there is something wrong with perm_list.push(arr)

Answer 1

I think I've found what your actual mistake is. You fill the result Array with the references to arr, so in the end the result looks like [arr, arr, arr, arr, arr ... arr]. You don't put a current copy there, you put a reference to your actual object you are working on and you change the same object afterwards. The key is to copy the current state of your arr into the separate object.

var A:Array = new Array;

permutations([1, 2, 3, 0], 0, A);

trace(A.join("\n"));

function permutations(values:Array, index:uint, result:Array):void
{
    var i:uint;
    var len:uint = values.length;

    if (index == len)
    {
        // Look at the ".slice()" here, it is why
        // this one is working as expected.
        result.push(values.slice());
        return;
    }

    for (i = index; i < len; i++)
    {
        swap(values, index, i);
        permutations(values, index + 1, result);
        swap(values, index, i);
    }
}

function swap(list:Array, from:uint, to:uint):void
{
    var temp:* = list[from];
    list[from] = list[to];
    list[to] = temp;
}