Как найти все подмножества набора в JavaScript?

Ответ 1

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

const getAllSubsets = 
      theArray => theArray.reduce(
        (subsets, value) => subsets.concat(
         subsets.map(set => [value,...set])
        ),
        [[]]
      );

console.log(getAllSubsets([1,2,3]));

Ответ 2

Мы можем решить эту проблему для подмножества входного массива, начиная со offset. Затем мы возвращаемся назад, чтобы получить полное решение.

Использование функции генератора позволяет нам перебирать подмножества с постоянным использованием памяти:

// Generate all array subsets:
function* subsets(array, offset = 0) {
  while (offset < array.length) {
    let first = array[offset++];
    for (let subset of subsets(array, offset)) {
      subset.push(first);
      yield subset;
    }
  }
  yield [];
}

// Example:
for (let subset of subsets([1, 2, 3])) {
  console.log(subset); 
}

Ответ 3

Еще одно простое решение.

function getCombinations(array) {

    function fork(i, t) {
        if (i === array.length) {
            result.push(t);
            return;
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }

    var result = [];
    fork(0, []);
    return result;
}

var data = [1, 2, 3],
    result = getCombinations(data);
	
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Ответ 4

Вы можете легко сгенерировать набор команд из массива, используя что-то вроде следующего:

var arr = [1, 2, 3];

function generatePowerSet(array) {
  var result = [];
  result.push([]);

  for (var i = 1; i < (1 << array.length); i++) {
    var subset = [];
    for (var j = 0; j < array.length; j++)
      if (i & (1 << j))
        subset.push(array[j]);

    result.push(subset);
  }

  return result;
}

console.log(generatePowerSet(arr));

Ответ 5

let subsets = (n) => {

let result = [];
result.push([]);

n.forEach(a => {

  //array length
   let length = result.length;
    let i =0;

    while(i < length){

      let temp = result[i].slice(0);
      temp.push(a);

      result.push(temp);
      i++;

    }
})

return result;
}

Ответ 6

Этот с рекурсией

var subsets = function(s){
  if(s.length === 0) {
    return [[]]
  }
  var h,t,ss_excl_h;
  var ss_incl_h = [];
  [h,...t] = s;
  ss_excl_h = subsets(t)
  for(ss of ss_excl_h) {
    let hArr = [];
    hArr.push(h);
    let temp = hArr.concat(ss)
    ss_incl_h.push(temp);
  }
  return ss_incl_h.concat(ss_excl_h)
}

console.log(subsets([1,2,3])) // returns distinct subsets