найти комбинации 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 );

Эта последняя часть должна печатать все (6 выберите 5) = 6 комбинаций из 5 элементов из keys.

Идея состоит в том, что теперь при каждом вызове функции splice удаляет только элемент, который был добавлен в этом вызове, а не что-то добавленное в каком-либо другом вызове функции, возможно, на каком-то другом уровне. Это также гарантирует, что a останется таким же в конце, как и в начале. (Все, что вы добавляете, вы снова удаляете.)

Это общий шаблон, который вы увидите при написании рекурсивных функций: сделайте некоторую модификацию, рекурсивно вызовите функцию, затем выполните некоторую очистку, которая перевернет модификацию.

Кстати, немного более чистый код (без обфускации cross = r-1) находится в первой редакции этого ответа .