数组全排列

如何输出一个数组全部可能的排列组合?

比如[1, 2],应该输出[1, 2][2, 1]

再比如[1, 2, 3],应该输出[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]

观察以上数据,其实可以推断出,假设一组数p = {r1, r2, r3, ..., rn},全排列表示为perm(p),数组中除rn之外的数据集合表示为pn = p - {rn}。

那么perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), …, rnperm(pn)。

数据全部可能的排列组合就是r1perm(p1),r2perm(p2),….,rnperm(pn)的集合。

算法:

1
// 对从k到m的子数组进行排列
perm(arr, k, m):
    if k > m
        // 递归结束,输出一个排列
        console.log(arr);
    else
        for i from k to m
            // 以arr[k]为开头的排列
            // 先将i处的数交换到k处
            // 那么剩下的数就为arr - {arr[k]}
            swap(arr, k, i)
            // 排列的问题就转换成arr[k]perm(arr, k + 1, m)
            perm(arr, k + 1, m)
            // 将原来的开头的数交换回去
            // 继续以数组下一项为开头的排列
            swap(arr, k, i)

js实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
define(
function (require) {
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}

function perm(arr, start, end, result) {
if (start > end) {
result.push(arr.slice(0));
}
else {
for (var i = start; i <= end; i++) {
swap(arr, start, i);
perm(arr, start + 1, end, result);
swap(arr, start, i);
}
}
return result;
}

return function (arr) {
var result = [];
perm(arr, 0, arr.length - 1, result);
return result;
};
}
);

使用方式:

1
2
3
4
require(['module-id'], function (perm) {
var result = perm([1, 2, 3]);
console.log(JSON.stringify(result));
});

输出[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2]