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

程序也比较简单：

var combinate = function(listArr, callback) {
    var result,
        temp,
        left,
        max = Math.pow(2, listArr.length),
        i;

    for (i = 1; i < max; i++) {
        temp = i;
        result = listArr.filter(function() {
            var result = false;
            left = temp % 2;
            if (left !== 0 && temp !== 0) {
                result = true;
            }
            temp = parseInt(temp / 2);

            return result;
        });

        callback(result);
    }
};

filter过滤数组结果，只有为true时才进入结果数组。

当然，这个明显没有考虑去重，没关系，接下来我们会在之后的程序中考虑去重的，先进入简单的排列，排列的思想是递归的交换前一项和后一项，算法比较神奇，但如果我们在草稿纸上仔细写下来，会发现真的是。之后就好办多了：

/**
 * 交换一个数组中的第i项和第j项（起始项为0）
 * @param arr
 * @param i
 * @param j
 */
var swap = function(arr, i, j) {
    var length = arr.length,
        temp;

    temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};

/**
 * 全排列使用的是递归交换数组中的数字
 * @param listArr
 * @param start 开始的值，调用时输入0
 * @param callback
 */
var permutate = function(listArr, start, callback) {
    var i,
        length = listArr.length;

    if (start === listArr.length - 1) {
        callback(listArr);
    } else {
        for (i = start; i < length; i++) {
            swap(listArr, start, i);
            permutate(listArr, start + 1, callback);
            swap(listArr, start, i);
        }
    }
};

循环中第二次交换是为了还原现场。

之后我们考虑除了[a, b, c]之外，还有可能是[a, b, b]的情况，因此我们需要对过程或者结果中进行去重，这里先从过程去重开始考虑。之后我们会说结果去重。

过程去重的算法主要考虑在交换过程中选中了相同内容，不同位置的字符，因此只要只选中他们中的一个，忽略其他即可，通常来说我们都选择特殊位置，第一个或者最后一个，那么只要判断是否是第一个或者最后一个即可。

/**
 * 检测是否可以交换
 * 查看交换的值在之后是否有重复出现，需求是只和特定的value仅交换一次，如果有重复则不交换
 * 此时有两种思路，一种是首次交换，之后抛弃所有同value的值（此时我们可以提供向前检测的方法）
 * 第二种是最后交换，在此之前所有值都不进行交换（这时我们使用向后检测的方法）
 * 这里我们使用向后检测，保证这是最后一个
 * @param arr
 * @param i
 * @param j
 */
var canSwap = function(arr, i, j) {
    return arr.slice(i, j).indexOf(arr[j]) === -1;
};

之后，在全排列中我们加入判断，即可达到去重的效果：

/**
 * 去重的全排列
 * @param listArr
 * @param start
 * @param callback
 */
var permutateWithoutTheSame = function(listArr, start, callback) {
    var i,
        length = listArr.length;

    if (start === listArr.length - 1) {
        callback(listArr);
    } else {
        for (i = start; i < length; i++) {
            // 检测是否需要交换
            if (canSwap(listArr, start, i)) {
                swap(listArr, start, i);
                arguments.callee(listArr, start + 1, callback);
                swap(listArr, start, i);
            }
        }
    }
};

这样挺直观，缺点是效率很低，毕竟每次都要找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开始的最左端，实现一次循环。

看懂了这个，接下来就能做了：

/**
 * 部分组合
 * 我们不需要全部的组合，只需要指定selectNum个空去进行组合
 * @param listArr
 * @param selectNum
 * @param callback
 */
var combinateWithoutAll = function(listArr ,selectNum, callback) {
    var listCount = [], // 计数器数组
        result = [],
        length = listArr.length,
        oneCount = 0,   // 统计出现过的1
        i,
        canPrint = true;

    init(listCount, selectNum, length - 1);

    while (checkEnd(listCount, selectNum)) {
        store(listArr, listCount, result);

        if (canPrint) {
            callback(result);
        }

        canPrint = true;

        for (i = 0; i < length; i++) {

            if (listCount[i] === 0 && oneCount !== 0) {

                listCount[i - 1] = 0;
                listCount[i] = 1;

                // 去除重复的无用项
                if (!canSwap(listArr, 0, i)) {
                    canPrint = false;
                }

                init(listCount, oneCount - 1, i - 2);
                oneCount = 0;
                break;

            } else if (listCount[i] === 1) {
                oneCount++;
            }

        }
    }


    store(listArr, listCount, result);
    callback(result);

    /**
     * 对 0 / 1结构进行初始化
     * 前num个为 1
     * 直到end为止为0
     * @param listCount
     * @param num
     * @param end
     */
    function init (listCount, num, end) {
        var i = 0;
        for (i = 0; i < num; i++) {
            listCount[i] = 1;
        }

        for (; i <= end; i++) {
            listCount[i] = 0;
        }
    }

    /**
     * 存储结果
     * @param listArr
     * @param listCount
     * @param result
     */
    function store(listArr, listCount, result) {
        var length = listCount.length,
            i,
            j = 0;

        for (i = 0; i < length; i++) {
            if (listCount[i] === 1) {
                result[j++] = listArr[i];
            }
        }
    }

    /**
     * 检查是否是最后一个组合情况
     * @param listCount
     * @param selectNum
     * @returns {boolean}
     */
    function checkEnd(listCount, selectNum) {
        var length = listCount.length,
            i = length - 1,
            end = length - selectNum;
        for (i = length - 1; i >= end; i--) {
            if (listCount[i] !== 1) {
                return true;
            }
        }

        return false;
    }
};

这里我们顺便实现了一个去重，如果不需要的话把去重的几行删掉即可（同时效率也提高了）。

对于排列，我们想到了一个办法：把组合进行全排列，将全排列函数作为回调传入即可。

另一种方法，对于全排列，选出每个排列中的前n项截断，之后进行去重。

这里我们说了半天的结果去重终于要登场了，我们使用一个利器：哈希表。在JavaScript也就是对象，我们把数组转换为字符串，作为index，然后把index取出即可。

/**
 * 利用全排列的思路，先截断后去重
 * @param listArr
 * @param selectorNum
 * @param callback
 */
var permutateWithoutAll = function(listArr, selectorNum, callback) {
    var resultHash = {},
        result = [],
        i = 0;

    permutateWithoutTheSame(listArr, 0, function(arr) {
        var index = arr.slice(0, selectorNum).join(',');
        resultHash[index] = '';
    });

    for (var index in resultHash) {
        if (resultHash.hasOwnProperty(index)) {
            result[i++] = index.split(',');
            callback(result[i - 1]);
        }
    }
};

效率比起原来肯定是高了不少，原来我们的去重也可以通过这个思路来处理。

之后我们用系统的time来统计了一下运行时间，发现大量时间都花在了去重上，确实在过程中去重还是很坑的，另外一点，由于是递归调用，容易stackoverflow，只能适合少量的排列，大量就不适合了，其他排列的方法以后有空再进行学习。

另外，如果只是需要一组随机字串，可以使用洗牌程序。

扩展阅读：

全排列和全组合实现

高效率的排列组合算法--《编程珠矶》--python实现

全排列的六种算法