¿Cómo generar iterativamente subconjuntos de elementos k a partir de un conjunto de tamaño n en java?

Estoy trabajando en un rompecabezas que implica analizar todos los subconjuntos k de tamaño y descubrir cuál es el óptimo. Escribí una solución que funciona cuando el número de subconjuntos es pequeño, pero se queda sin memoria para problemas más grandes. Ahora trato de traducir una función iterativa escrita en python a java para poder analizar cada subconjunto a medida que se crea y obtener solo el valor que representa qué tan optimizado es y no el conjunto completo para que no me quede sin memoria. Esto es lo que tengo hasta ahora y no parece terminar incluso para problemas muy pequeños:

public static LinkedList<LinkedList> getSets(int k, LinkedList set) { int N = set.size(); int maxsets = nCr(N, k); LinkedList<LinkedList> toRet = new LinkedList<LinkedList>(); int remains, thresh; LinkedList newset; for (int i=0; i<maxsets; i++) { remains = k; newset = new LinkedList(); for (int val=1; val<=N; val++) { if (remains==0) break; thresh = nCr(N-val, remains-1); if (i < thresh) { newset.add(set.get(val-1)); remains --; } else { i -= thresh; } } toRet.add(newset); } return toRet; } 

¿Alguien puede ayudarme a depurar esta función o sugerir otro algoritmo para generar iterativamente subconjuntos de tamaño k?

EDITAR: finalmente conseguí que esta función funcionara, tuve que crear una nueva variable que fuera lo mismo que yo para hacer la comparación i y trilla porque Python maneja los índices de ciclo de manera diferente.

En primer lugar, si tiene la intención de hacer acceso aleatorio en una lista, debe elegir una implementación de lista que lo soporte de manera eficiente. Desde javadoc en LinkedList:

Todas las operaciones funcionan como se podría esperar para una lista doblemente enlazada. Las operaciones que indizan en la lista atravesarán la lista desde el principio o el final, lo que esté más cerca del índice especificado.

Un ArrayList es más eficiente en el uso del espacio y mucho más rápido para el acceso aleatorio. En realidad, dado que conoce la longitud de antemano, incluso puede usar una matriz simple.

Para los algoritmos: Comencemos simple: ¿cómo generaría todos los subconjuntos de tamaño 1? Probablemente así:

 for (int i = 0; i < set.length; i++) { int[] subset = {i}; process(subset); } 

Donde el proceso es un método que hace algo con el conjunto, como comprobar si es "mejor" que todos los subconjuntos procesados ​​hasta el momento.

Ahora, ¿cómo extenderías eso para trabajar en subconjuntos de tamaño 2? ¿Cuál es la relación entre subconjuntos de tamaño 2 y subconjuntos de tamaño 1? Bueno, cualquier subconjunto de tamaño 2 se puede convertir en un subconjunto de tamaño 1 eliminando su elemento más grande. Dicho de otra manera, cada subconjunto de tamaño 2 se puede generar tomando un subconjunto de tamaño 1 y agregando un nuevo elemento más grande que todos los otros elementos en el conjunto. En codigo:

 processSubset(int[] set) { int subset = new int[2]; for (int i = 0; i < set.length; i++) { subset[0] = set[i]; processLargerSets(set, subset, i); } } void processLargerSets(int[] set, int[] subset, int i) { for (int j = i + 1; j < set.length; j++) { subset[1] = set[j]; process(subset); } } 

Para subconjuntos de tamaño arbitrario k, observe que cualquier subconjunto de tamaño k se puede convertir en un subconjunto de tamaño k-1 cortando el elemento más grande. Es decir, todos los subconjuntos de tamaño k pueden generarse generando todos los subconjuntos de tamaño k - 1, y para cada uno de ellos, y cada valor mayor que el más grande del subconjunto, agregue ese valor al conjunto. En codigo:

 static void processSubsets(int[] set, int k) { int[] subset = new int[k]; processLargerSubsets(set, subset, 0, 0); } static void processLargerSubsets(int[] set, int[] subset, int subsetSize, int nextIndex) { if (subsetSize == subset.length) { process(subset); } else { for (int j = nextIndex; j < set.length; j++) { subset[subsetSize] = set[j]; processLargerSubsets(set, subset, subsetSize + 1, j + 1); } } } 

Código de prueba:

 static void process(int[] subset) { System.out.println(Arrays.toString(subset)); } public static void main(String[] args) throws Exception { int[] set = {1,2,3,4,5}; processSubsets(set, 3); } 

Pero antes de invocar esto en conjuntos grandes, recuerde que la cantidad de subconjuntos puede crecer bastante rápido.

Puedes usar org.apache.commons.math3.util.Combinations .

Ejemplo:

 import java.util.Arrays; import java.util.Iterator; import org.apache.commons.math3.util.Combinations; public class tmp { public static void main(String[] args) { for (Iterator iter = new Combinations(5, 3).iterator(); iter.hasNext();) { System.out.println(Arrays.toString(iter.next())); } } } 

Salida: [0, 1, 2] [0, 1, 3] [0, 2, 3] [1, 2, 3] [0, 1, 4] [0, 2, 4] [1, 2, 4 ] [0, 3, 4] [1, 3, 4] [2, 3, 4]

He tenido el mismo problema hoy, de generar todos los subconjuntos de tamaño k de un conjunto de tamaño n .

Tenía un algoritmo recursivo, escrito en Haskell, pero el problema requería que escribiera una nueva versión en Java.
En Java, pensé que probablemente tendría que usar memoria para optimizar la recursividad. Resulta que encontré una manera de hacerlo iterativamente. Me inspiré en esta imagen , de Wikipedia, en el artículo sobre Combinaciones.

Método para calcular todos los subconjuntos del tamaño k :

 public static int[][] combinations(int k, int[] set) { // binomial(N, K) int c = (int) binomial(set.length, k); // where all sets are stored int[][] res = new int[c][Math.max(0, k)]; // the k indexes (from set) where the red squares are // see image above int[] ind = k < 0 ? null : new int[k]; // initialize red squares for (int i = 0; i < k; ++i) { ind[i] = i; } // for every combination for (int i = 0; i < c; ++i) { // get its elements (red square indexes) for (int j = 0; j < k; ++j) { res[i][j] = set[ind[j]]; } // update red squares, starting by the last int x = ind.length - 1; boolean loop; do { loop = false; // move to next ind[x] = ind[x] + 1; // if crossing boundaries, move previous if (ind[x] > set.length - (k - x)) { --x; loop = x >= 0; } else { // update every following square for (int x1 = x + 1; x1 < ind.length; ++x1) { ind[x1] = ind[x1 - 1] + 1; } } } while (loop); } return res; } 

Método para el binomio:
(Adaptado del ejemplo de Python, de Wikipedia)

 private static long binomial(int n, int k) { if (k < 0 || k > n) return 0; if (k > n - k) { // take advantage of symmetry k = n - k; } long c = 1; for (int i = 1; i < k+1; ++i) { c = c * (n - (k - i)); c = c / i; } return c; } 

Por supuesto, las combinaciones siempre tendrán el problema del espacio, ya que es probable que exploten.
En el contexto de mi propio problema, el máximo posible es de aproximadamente 2,000,000 de subconjuntos. Mi máquina calculó esto en 1032 milisegundos.

Inspirado por la respuesta de afsantos: -) … Decidí escribir una implementación C .NET para generar todas las combinaciones de subconjuntos de un cierto tamaño a partir de un conjunto completo. No es necesario calcular el número total de subconjuntos posibles; detecta cuando se llega al final. Aquí está:

 public static List generateAllSubsetCombinations(object[] fullSet, ulong subsetSize) { if (fullSet == null) { throw new ArgumentException("Value cannot be null.", "fullSet"); } else if (subsetSize < 1) { throw new ArgumentException("Subset size must be 1 or greater.", "subsetSize"); } else if ((ulong)fullSet.LongLength < subsetSize) { throw new ArgumentException("Subset size cannot be greater than the total number of entries in the full set.", "subsetSize"); } // All possible subsets will be stored here List allSubsets = new List(); // Initialize current pick; will always be the leftmost consecutive x where x is subset size ulong[] currentPick = new ulong[subsetSize]; for (ulong i = 0; i < subsetSize; i++) { currentPick[i] = i; } while (true) { // Add this subset's values to list of all subsets based on current pick object[] subset = new object[subsetSize]; for (ulong i = 0; i < subsetSize; i++) { subset[i] = fullSet[currentPick[i]]; } allSubsets.Add(subset); if (currentPick[0] + subsetSize >= (ulong)fullSet.LongLength) { // Last pick must have been the final 3; end of subset generation break; } // Update current pick for next subset ulong shiftAfter = (ulong)currentPick.LongLength - 1; bool loop; do { loop = false; // Move current picker right currentPick[shiftAfter]++; // If we've gotten to the end of the full set, move left one picker if (currentPick[shiftAfter] > (ulong)fullSet.LongLength - (subsetSize - shiftAfter)) { if (shiftAfter > 0) { shiftAfter--; loop = true; } } else { // Update pickers to be consecutive for (ulong i = shiftAfter+1; i < (ulong)currentPick.LongLength; i++) { currentPick[i] = currentPick[i-1] + 1; } } } while (loop); } return allSubsets; } 

Esta solución funcionó para mí:

  private static void findSubsets(int array[]) { int numOfSubsets = 1 << array.length; for(int i = 0; i < numOfSubsets; i++) { int pos = array.length - 1; int bitmask = i; System.out.print("{"); while(bitmask > 0) { if((bitmask & 1) == 1) System.out.print(array[pos]+","); bitmask >>= 1; pos--; } System.out.print("}"); } } 

Aquí hay un iterador de combinación que escribí recetnly

 package psychicpoker; import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; import java.util.List; import static com.google.common.base.Preconditions.checkArgument; public class CombinationIterator implements Iterator> { private int[] indices; private List elements; private boolean hasNext = true; public CombinationIterator(List elements, int k) throws IllegalArgumentException { checkArgument(k<=elements.size(), "Impossible to select %d elements from hand of size %d", k, elements.size()); this.indices = new int[k]; for(int i=0; i next() { Collection result = new ArrayList(indices.length); for(int i=indices.length-1; i>=0; i--) { result.add(elements.get(indices[i])); } hasNext = inc(); return result; } public void remove() { throw new UnsupportedOperationException(); } 

}

Implementación rápida:

A continuación hay dos variantes de la respuesta proporcionada por afsantos .

La primera implementación de la función de combinations refleja la funcionalidad de la implementación original de Java.

La segunda implementación es un caso general para encontrar todas las combinaciones de valores k del conjunto [0, setSize) . Si esto es realmente todo lo que necesita, esta implementación será un poco más eficiente.

Además, incluyen algunas optimizaciones menores y una simplificación lógica smidgin.

 /// Calculate the binomial for a set with a subset size func binomial(setSize: Int, subsetSize: Int) -> Int { if (subsetSize <= 0 || subsetSize > setSize) { return 0 } // Take advantage of symmetry var subsetSizeDelta = subsetSize if (subsetSizeDelta > setSize - subsetSizeDelta) { subsetSizeDelta = setSize - subsetSizeDelta } // Early-out if subsetSizeDelta == 0 { return 1 } var c = 1 for i in 1...subsetSizeDelta { c = c * (setSize - (subsetSizeDelta - i)) c = c / i } return c } /// Calculates all possible combinations of subsets of `subsetSize` values within `set` func combinations(subsetSize: Int, set: [Int]) -> [[Int]]? { // Validate inputs if subsetSize <= 0 || subsetSize > set.count { return nil } // Use a binomial to calculate total possible combinations let comboCount = binomial(setSize: set.count, subsetSize: subsetSize) if comboCount == 0 { return nil } // Our set of combinations var combos = [[Int]]() combos.reserveCapacity(comboCount) // Initialize the combination to the first group of set indices var subsetIndices = [Int](0.. set.count - (subsetSize - x)) { x -= 1 if x >= 0 { continue } } else { for x1 in x+1.. [[Int]]? { // Validate inputs if subsetSize <= 0 || subsetSize > setSize { return nil } // Use a binomial to calculate total possible combinations let comboCount = binomial(setSize: setSize, subsetSize: subsetSize) if comboCount == 0 { return nil } // Our set of combinations var combos = [[Int]]() combos.reserveCapacity(comboCount) // Initialize the combination to the first group of elements var subsetValues = [Int](0.. setSize - (subsetSize - x)) { x -= 1 if x >= 0 { continue } } else { for x1 in x+1..