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.