js实现简单排列组合的方法

下面是详细讲解 "js实现简单排列组合的方法" 的攻略。

排列组合的概念

排列就是由给定的n个元素中取出m（m ≤ n）个元素的所有排列总数的不同的排列数，用A(n, m)表示。例如，有3个元素A、B、C，则它们的排列有：ABC、ACB、BAC、BCA、CAB、CBA，共6种排列。

组合是指从n个不同元素中，取出m（m≤n）个元素的所有组合情况，用C(n,m)表示。

排列算法实现

以下是一个生成一个序列中所有排列的JavaScript函数：

function generatePerm(arr) { 
    var permutations = [], 
        usedChars = []; 
    function permute(arr) { 
        var i, ch; 
        for (i = 0; i < arr.length; i++) { 
            ch = arr.splice(i, 1)[0]; 
            usedChars.push(ch); 
            if (arr.length === 0) { 
                permutations.push(usedChars.slice());  
            } 
            permute(arr); 
            arr.splice(i, 0, ch); 
            usedChars.pop(); 
        } 
        return permutations; 
    } 
    return permute(arr); 
} 

使用方法

var arr = [1, 2, 3]; 
console.log(generatePerm(arr));

输出：

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 

以上算法中，使用一个递归函数permute，将数组中的每个元素当作起始元素，以此生成不同的排列。

组合算法实现

以下是一个生成一个序列中所有组合的JavaScript函数：

function generateComb(arr, numElements) { 
    var results = [], 
        result = []; 
    function combine(arr, numElements, pos) { 
        if (result.length === numElements) { 
            results.push(result.slice()); 
            return; 
        } 
        for (var i = pos; i < arr.length; i++) { 
            result.push(arr[i]); 
            combine(arr, numElements, i+1); 
            result.pop(); 
        } 
    } 
    combine(arr, numElements, 0); 
    return results; 
} 

使用方法：

var arr = [1, 2, 3]; 
console.log(generateComb(arr, 2));

输出：

[[1, 2], [1, 3], [2, 3]] 

以上算法中，使用一个递归函数combine，从数组的第一个元素开始，逐个把元素加入结果数组，如果元素加满了，就把该组合加入结果集。如果还没加满，就继续往后递归。需要注意的是，递归时的pos参数表示起始位置，要逐个枚举数组中剩余的元素。