Найти комбинацию подмножеств в массиве - PullRequest
Новая
       14

Найти комбинацию подмножеств в массиве

1 голос
/ 06 апреля 2019

У меня трудности с этой конкретной проблемой.

Меня попросили найти комбинацию подмножеств, которые имеют строго на один элемент меньше входного массива. Например из массива: 

var num = [1,2,3,4,5]

Найдите эти комбинации: 

[1,2,3,4]
[2,3,4,5]
[1,2,4,5]
[1,2,3,5]
[1,3,4,5]

и из этого массива: 

var num = [2,4,6]

Найдите эти комбинации: 

[2,4]
[2,6]
[4,6]

Я уже пробовал этот код, но он не является динамическим, поскольку я должен печатать каждый индекс массива: 

var num = [1,2,3,4,5];
var n = num.length;
var i, j;

for(i = 0; i < n; i++){
    for(j = i + 1; j < n; j++){
        console.log(num[i] + ", " +  num[j]);
    }
}

Есть ли способ сделать это? Заранее спасибо.

Ответы [ 3 ]

7 голосов
/ 06 апреля 2019

Поскольку вы просто удаляете один элемент для каждого результата, у вас будет результат для каждого элемента в исходном списке. Вы можете просто map() и slice(): 

const remove = (num) => num.map((_, i, arr) => [...arr.slice(0, i), ...arr.slice(i+1)])

console.log(remove([1,2,3,4,5]))
console.log(remove([2, 4, 6]))
4 голосов
/ 06 апреля 2019

Вы можете взять генератор и взять только один элемент или результат. 

function* getCombinations(array, length, left = []) {
    var i = 0;
    if (!length) yield left;
    while (i < array.length) {
        yield* getCombinations(array.slice(i + 1), length - 1, [...left, array[i]]);
        i++;
    }
}

console.log([...getCombinations([1, 2, 3, 4, 5], 4)].map(a => a.join(' ')));
console.log([...getCombinations([2, 4, 6], 2)].map(a => a.join(' ')));
console.log([...getCombinations([1, 2, 3, 4, 5], 3)].map(a => a.join(' ')));  // not asked
.as-console-wrapper { max-height: 100% !important; top: 0; }

Для удаления только одного элемента вы можете отфильтровать массив. 

function* getCombinations(array) {
    var l = array.length;
    while (l--) yield array.filter((_, i) => i !== l);
}

console.log([...getCombinations([1, 2, 3, 4, 5], 4)].map(a => a.join(' ')));
console.log([...getCombinations([2, 4, 6], 2)].map(a => a.join(' ')));
.as-console-wrapper { max-height: 100% !important; top: 0; }
2 голосов
/ 06 апреля 2019

Вы можете сделать что-то вроде:

Зацикливать массив и удалять его каждый раз 

// Function to return an array except the given one
Array.prototype.except = function(val) {
    return this.filter(function(x) { return x !== val; });        
}; 


// For array of 5
var array1 = [1,2,3,4,5]
var result1 = []

array1.forEach(function(val){
  result1.push(array1.except(val))
});

console.log('For Array of 5')
console.log(result1)


// For array of 3

var num = [2,4,6]
var num_result = []
num.forEach(function(val){
  num_result.push(num.except(val))
});
console.log('For Array of 3')
console.log(num_result)
...