javascript - simbolos - teoria de conjuntos pdf

Generar subconjuntos de longitud n

Question

Dado un Set , genere todos los subconjuntos de longitud n.

• Muestra de entrada:

  set = new Set([''a'', ''b'', ''c'']), length = 2

• Muestra de salida:

  Set {''a'', ''b''}, Set {''a'', ''c''}, Set {''b'', ''c''}

¿Cómo hacer esto de manera eficiente, sin convertir el Set en una Array ?

Ya tengo una buena solución para matrices como entrada:

function* subsets(array, length, start = 0) {
if (start >= array.length || length < 1) {
yield new Set();
} else {
while (start <= array.length - length) {
let first = array[start];
for (subset of subsets(array, length - 1, start + 1)) {
subset.add(first);
yield subset;
}
++start;
}
}
}
let array = [''a'', ''b'', ''c'', ''d''];
for (subset of subsets(array, 2)) {
console.log(...subset);
}

Sin embargo, no pude encontrar una implementación eficiente para los conjuntos sin convertir el conjunto en una matriz, lo que me gustaría evitar a favor de, por ejemplo, el uso exclusivo de iteradores.

Answer 1

Implementé su idea de eliminar y reinsertar valores con subconjuntos múltiples ordenados:

function orderedMultiSubsets(set, n) {
if(!Number.isInteger(n) || n < 0) return function*(){}();
var subset = new Array(n),
iterator = set.values();
return (function* backtrack(index) {
if(index === n) {
yield subset.slice();
} else {
for(var i=0; i<set.size; ++i) {
subset[index] = iterator.next().value; /* Get first item */
set.delete(subset[index]); /* Remove it */
set.add(subset[index]); /* Insert it at the end */
yield* backtrack(index+1);
}
}
})(0);
}
for(var subset of orderedMultiSubsets(new Set([1,2,3]), 2)) {
console.log(subset.join());
}

Y luego creo que logré podar lo más temprano posible para el caso de subconjuntos no ordenados:

function subsets(set, n) {
if(!Number.isInteger(n) || n < 0 || n > set.size) return function*(){}();
var subset = new Array(n),
iterator = set.values();
return (function* backtrack(index, remaining) {
if(index === n) {
yield subset.slice();
} else {
for(var i=0; i<set.size; ++i) {
subset[index] = iterator.next().value; /* Get first item */
set.delete(subset[index]); /* Remove it */
set.add(subset[index]); /* Insert it at the end */
if(i <= remaining) {
yield* backtrack(index+1, remaining-i);
}
}
}
})(0, set.size-n);
}
for(var subset of subsets(new Set([1,2,3,4]), 2)) {
console.log(subset.join());
}

Aún utilizo una matriz para los subconjuntos, pero su tamaño es solo n . Entonces, en caso de que el tamaño del conjunto sea mucho mayor que n , este enfoque podría usar menos memoria que duplicar el conjunto en una matriz, que supongo que es el punto de su pregunta. Pero tenga en cuenta que las eliminaciones e inserciones son probablemente más costosas que las búsquedas en arreglos.

Bonificación: al final, el orden del conjunto es el mismo que antes de llamar a la función.