JavaScript 排列与组合
排列与组合在我们日常生活中其实也是挺常用的，包括在算法中，也算是比较实用的东西，但是排列组合也是一个难点，这里我们先从简单的出发。
最简单的是全排列和全组合，其中组合的思路更加简单易行，因此我们先从全组合说起。
在说之前，我们先来确定一下定义（数学渣只能从自己下定义开始以免误导读者），我们的全排列，指的是PNN，也就是有n个数字，坑也有n个，求全部的排列情况；全组合，则是除了空集外，n个字母能组成多少种可能性（不一定要全部使用）。
由此，我们开始了我们的全组合之旅：
首先，我们考虑，假设有n个字母，我们将其使用标记为1，没有使用过标记为0.则可以得出[a, b, c] [0, 0, 1]=> [c]。那么同理，我们很快就能够列出所有的情况，就是把1和0全部尝试一遍，那么当abc时，数组为全1，此时，其实我们就能够想到，跟二进制非常像，全1时为7，全0为0。
那么问题就简单了，就是把全组合转换为到n的二进制，将二进制对应的结果输出：
简单列表来说明问题：
c b a
0 0 1 => a
0 1 0 => b
0 1 1 => ab
1 0 0 => c
1 0 1 => ca
1 1 0 => cb
1 1 1 => abc
程序也比较简单：
1var combinate = function(listArr, callback) {
2 var result,
3 temp,
4 left,
5 max = Math.pow(2, listArr.length),
6 i;
7
8 for (i = 1; i < max; i++) {
9 temp = i;
10 result = listArr.filter(function() {
11 var result = false;
12 left = temp % 2;
13 if (left !== 0 && temp !== 0) {
14 result = true;
15 }
16 temp = parseInt(temp / 2);
17
18 return result;
19 });
20
21 callback(result);
22 }
23};
24
filter过滤数组结果，只有为true时才进入结果数组。
当然，这个明显没有考虑去重，没关系，接下来我们会在之后的程序中考虑去重的，先进入简单的排列，排列的思想是递归的交换前一项和后一项，算法比较神奇，但如果我们在草稿纸上仔细写下来，会发现真的是。之后就好办多了：
1/**
2 * 交换一个数组中的第i项和第j项（起始项为0）
3 * @param arr
4 * @param i
5 * @param j
6 */
7var swap = function(arr, i, j) {
8 var length = arr.length,
9 temp;
10
11 temp = arr[i];
12 arr[i] = arr[j];
13 arr[j] = temp;
14};
15
16/**
17 * 全排列使用的是递归交换数组中的数字
18 * @param listArr
19 * @param start 开始的值，调用时输入0
20 * @param callback
21 */
22var permutate = function(listArr, start, callback) {
23 var i,
24 length = listArr.length;
25
26 if (start === listArr.length - 1) {
27 callback(listArr);
28 } else {
29 for (i = start; i < length; i++) {
30 swap(listArr, start, i);
31 permutate(listArr, start + 1, callback);
32 swap(listArr, start, i);
33 }
34 }
35};
36
循环中第二次交换是为了还原现场。
之后我们考虑除了[a, b, c]之外，还有可能是[a, b, b]的情况，因此我们需要对过程或者结果中进行去重，这里先从过程去重开始考虑。之后我们会说结果去重。
过程去重的算法主要考虑在交换过程中选中了相同内容，不同位置的字符，因此只要只选中他们中的一个，忽略其他即可，通常来说我们都选择特殊位置，第一个或者最后一个，那么只要判断是否是第一个或者最后一个即可。
1/**
2 * 检测是否可以交换
3 * 查看交换的值在之后是否有重复出现，需求是只和特定的value仅交换一次，如果有重复则不交换
4 * 此时有两种思路，一种是首次交换，之后抛弃所有同value的值（此时我们可以提供向前检测的方法）
5 * 第二种是最后交换，在此之前所有值都不进行交换（这时我们使用向后检测的方法）
6 * 这里我们使用向后检测，保证这是最后一个
7 * @param arr
8 * @param i
9 * @param j
10 */
11var canSwap = function(arr, i, j) {
12 return arr.slice(i, j).indexOf(arr[j]) === -1;
13};
14
之后，在全排列中我们加入判断，即可达到去重的效果：
1/**
2 * 去重的全排列
3 * @param listArr
4 * @param start
5 * @param callback
6 */
7var permutateWithoutTheSame = function(listArr, start, callback) {
8 var i,
9 length = listArr.length;
10
11 if (start === listArr.length - 1) {
12 callback(listArr);
13 } else {
14 for (i = start; i < length; i++) {
15 // 检测是否需要交换
16 if (canSwap(listArr, start, i)) {
17 swap(listArr, start, i);
18 arguments.callee(listArr, start + 1, callback);
19 swap(listArr, start, i);
20 }
21 }
22 }
23};
24
这样挺直观，缺点是效率很低，毕竟每次都要找index，相当于循环了一遍，相当耗时，在结果去重中，我们将选择更快的方式。
先来说说一般的排列和组合，我们发现，排列或者组合，这个程度的还是不足以满足我们的需求，毕竟平时组合我们可能是固定个数的，排列也不一定要求全排列。
还是先从组合开始，我们依旧从二进制下手：
可以来看一下这一段：
1 2 3 4 5
1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5
以上是他的全组合，我们可以看到，找到1前面的0，与其交换，把其他1归于从0开始的最左端，实现一次循环。
看懂了这个，接下来就能做了：
1/**
2 * 部分组合
3 * 我们不需要全部的组合，只需要指定selectNum个空去进行组合
4 * @param listArr
5 * @param selectNum
6 * @param callback
7 */
8var combinateWithoutAll = function(listArr ,selectNum, callback) {
9 var listCount = [], // 计数器数组
10 result = [],
11 length = listArr.length,
12 oneCount = 0, // 统计出现过的1
13 i,
14 canPrint = true;
15
16 init(listCount, selectNum, length - 1);
17
18 while (checkEnd(listCount, selectNum)) {
19 store(listArr, listCount, result);
20
21 if (canPrint) {
22 callback(result);
23 }
24
25 canPrint = true;
26
27 for (i = 0; i < length; i++) {
28
29 if (listCount[i] === 0 && oneCount !== 0) {
30
31 listCount[i - 1] = 0;
32 listCount[i] = 1;
33
34 // 去除重复的无用项
35 if (!canSwap(listArr, 0, i)) {
36 canPrint = false;
37 }
38
39 init(listCount, oneCount - 1, i - 2);
40 oneCount = 0;
41 break;
42
43 } else if (listCount[i] === 1) {
44 oneCount++;
45 }
46
47 }
48 }
49
50
51 store(listArr, listCount, result);
52 callback(result);
53
54 /**
55 * 对 0 / 1结构进行初始化
56 * 前num个为 1
57 * 直到end为止为0
58 * @param listCount
59 * @param num
60 * @param end
61 */
62 function init (listCount, num, end) {
63 var i = 0;
64 for (i = 0; i < num; i++) {
65 listCount[i] = 1;
66 }
67
68 for (; i <= end; i++) {
69 listCount[i] = 0;
70 }
71 }
72
73 /**
74 * 存储结果
75 * @param listArr
76 * @param listCount
77 * @param result
78 */
79 function store(listArr, listCount, result) {
80 var length = listCount.length,
81 i,
82 j = 0;
83
84 for (i = 0; i < length; i++) {
85 if (listCount[i] === 1) {
86 result[j++] = listArr[i];
87 }
88 }
89 }
90
91 /**
92 * 检查是否是最后一个组合情况
93 * @param listCount
94 * @param selectNum
95 * @returns {boolean}
96 */
97 function checkEnd(listCount, selectNum) {
98 var length = listCount.length,
99 i = length - 1,
100 end = length - selectNum;
101 for (i = length - 1; i >= end; i--) {
102 if (listCount[i] !== 1) {
103 return true;
104 }
105 }
106
107 return false;
108 }
109};
110
这里我们顺便实现了一个去重，如果不需要的话把去重的几行删掉即可（同时效率也提高了）。
对于排列，我们想到了一个办法：把组合进行全排列，将全排列函数作为回调传入即可。
另一种方法，对于全排列，选出每个排列中的前n项截断，之后进行去重。
这里我们说了半天的结果去重终于要登场了，我们使用一个利器：哈希表。在JavaScript也就是对象，我们把数组转换为字符串，作为index，然后把index取出即可。
1/**
2 * 利用全排列的思路，先截断后去重
3 * @param listArr
4 * @param selectorNum
5 * @param callback
6 */
7var permutateWithoutAll = function(listArr, selectorNum, callback) {
8 var resultHash = {},
9 result = [],
10 i = 0;
11
12 permutateWithoutTheSame(listArr, 0, function(arr) {
13 var index = arr.slice(0, selectorNum).join(',');
14 resultHash[index] = '';
15 });
16
17 for (var index in resultHash) {
18 if (resultHash.hasOwnProperty(index)) {
19 result[i++] = index.split(',');
20 callback(result[i - 1]);
21 }
22 }
23};
24
效率比起原来肯定是高了不少，原来我们的去重也可以通过这个思路来处理。
之后我们用系统的time来统计了一下运行时间，发现大量时间都花在了去重上，确实在过程中去重还是很坑的，另外一点，由于是递归调用，容易stackoverflow，只能适合少量的排列，大量就不适合了，其他排列的方法以后有空再进行学习。
另外，如果只是需要一组随机字串，可以使用洗牌程序。
扩展阅读：
评论 (0)