如何在 Actionscript 3.0 中获取数组的所有排列?
How to get an array all permutation in Actionscript 3.0?
假设我有一个数组 A = [0,1,2]。如何获得二维数组 perm_A = [[0,1,2],[0,2,1][1,0,2][1,2,0][2,1,0 ],[2,0,1]? perm_A 中排列应用程序的顺序无关紧要。
我使用了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])
}
结果是:
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
这显然是错误的。
更新
如果我改变perm_list.push(arr);跟踪(arr),我确实得到了正确的结果。但是,这只会输出控制台中的所有排列。我想将所有这些排列收集到一个二维数组中。
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);
输出
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
我猜 perm_list.push(arr)
似乎有问题
我想我发现了你真正的错误所在。你用对 arr 的引用填充结果 Array,所以最终结果看起来像 [arr, arr, arr , arr, arr ... arr]。您不会在那里放置当前副本,而是放置对您正在处理的实际对象的引用,然后更改同一个对象。关键是将 arr 的当前状态复制到单独的对象中。
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;
}
假设我有一个数组 A = [0,1,2]。如何获得二维数组 perm_A = [[0,1,2],[0,2,1][1,0,2][1,2,0][2,1,0 ],[2,0,1]? perm_A 中排列应用程序的顺序无关紧要。
我使用了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])
}
结果是:
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
这显然是错误的。
更新
如果我改变perm_list.push(arr);跟踪(arr),我确实得到了正确的结果。但是,这只会输出控制台中的所有排列。我想将所有这些排列收集到一个二维数组中。
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);
输出
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
我猜 perm_list.push(arr)
似乎有问题我想我发现了你真正的错误所在。你用对 arr 的引用填充结果 Array,所以最终结果看起来像 [arr, arr, arr , arr, arr ... arr]。您不会在那里放置当前副本,而是放置对您正在处理的实际对象的引用,然后更改同一个对象。关键是将 arr 的当前状态复制到单独的对象中。
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;
}