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实现

全排列的六种算法

如果您觉得文章不错,可以通过赞助支持我

标签: 知识, 算法

添加新评论