Saltar al contenido

¿Cómo encontrar todos los subconjuntos de un conjunto en JavaScript?

Te traemos la respuesta a este asunto, al menos eso creemos. Si tienes preguntas puedes dejarlo en el apartado de comentarios, que sin dudar

Solución:

Aquí hay una solución más muy elegante sin bucles ni recursividad, solo usando el mapa y reduce array funciones nativas.

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

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

Podemos resolver este problema para un subconjunto de la entrada arrayempezando desde offset. Luego recurrimos para obtener una solución completa.

El uso de una función de generador nos permite iterar a través de subconjuntos con un uso de memoria constante:

// 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); 

La complejidad del tiempo de ejecución es proporcional al número de soluciones (2ⁿ) multiplicado por la duración promedio por solución (n/2) = O(n2ⁿ).

Otra solución sencilla.

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; 

Te mostramos reseñas y puntuaciones

Si conservas algún reparo o capacidad de prosperar nuestro post eres capaz de realizar un comentario y con mucho gusto lo ojearemos.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *