查找数组项的nCr组合

Question

在数组中查找nCr对象的递归函数有问题。

这只在r=2时起作用，意味着只有在内部达到1级时才能起作用。

我的临时'a'数组似乎在r > 2的时候搞砸了

// find nCr combinations in Array
// n -> keys.length
// r -> number of combination to extract (cross = r-1 )

console.clear();
var keys = [0,1,2,3,4,5];

// cross = 'r'-1, s = start point, a = array
function recursive(cross, s, a){
    for( var i=s; i < keys.length; i++ ){
        if( !cross ){
            var b = a.slice(0);
            b.push( keys[i] );
            set.push( b );
        }
        else{ 
            a.splice(-1, 1);
            a.push(keys[i]); 
            recursive(cross-1, i+1, a); 
        }
    }
}

var set = [];
recursive(1, 0, []);
console.log( set );

Answer 1

我不知道您在else条件下到底要做什么:注意，a.splice(-1,1)删除了a的最后一个元素，但是在没有要删除的情况下，从a空开始。即使代码适用于r=2，这也表明您正在做一些错误的事情。(实际上，每次您深入一个级别时，a的开头元素数与前一个级别相同，因此您要删除一些不应该触及的元素。)

下面是对您的算法的一个非常小的修改，它正确地工作。我只是更改了else条件中语句的顺序。

var keys = [0,1,2,3,4,5];

function recursive(cross, s, a) {
    for( var i=s; i < keys.length; i++ ){
        if( !cross ){
            var b = a.slice(0);
            b.push( keys[i] );
            set.push( b );
        }
        else{ 
            a.push(keys[i]); 
            recursive(cross-1, i+1, a); 
            a.splice(-1, 1);
        }
    }
}

var set = [];
recursive(4, 0, []);
console.log( set );

最后一部分应该从keys中打印所有(6选择5)=6组合的5个元素。

其思想是，在函数的每个调用中，splice只删除在该调用中添加的元素，而不是在其他函数调用中添加的内容(可能在其他级别)。这也保证了a在结束时和开始时保持不变。(您添加的所有内容再次删除。)

在编写递归函数时，您将看到这样一种常见模式:执行一些修改，递归调用该函数，然后执行一些与修改相反的清理。

顺便说一句，稍微干净一点的代码(没有cross = r-1混淆)在the first revision of this answer中。