k-combinaciones de un conjunto de números enteros en orden ascendente de orden

Question

Desafío de programación: dado un conjunto de enteros [1, 2, 3, 4, 5] Me gustaría generar todas las k-combinaciones posibles en orden de tamaño ascendente en Java; p.ej.

[1], [2], [3], [4], [5], [1, 2], [1, 3] ... [1, 2, 3, 4, 5] 

Es bastante fácil de producir una solución recursiva que genera todas las combinaciones y luego ordenarlos después, pero me imagino que hay una manera más eficiente que elimina la necesidad de la clase adicional.

Answer 1

Estaba pensando en esto un poco más y me di cuenta de que se puede hacer de manera eficiente utilizando un enfoque de programación dinámica. A continuación se muestra la solución iterativa que he producido, que utiliza un Queue para mantener el estado (aunque en su lugar se podría usar un Stack).

Creo que esto es mucho más eficiente que una búsqueda recursiva de profundización iterativa, ya que no implicará volver a visitar estados existentes durante la generación; recuerda los estados anteriores usando la cola y los usa para generar estados sucesivos.

Comparación de rendimiento

Algorithm     | 5 elems | 10 elems | 20 elems 
-------------------------------------------------------------------------- 
Recursive (#recursions)  | 62  | 2046  | 2097150 
Dynamic (#loop iterations) | 32  | 1024  | 1048576 

Código

public class Test { 
    private static class Pair { 
     private final List<Integer> result; 
     private final int index; 

     private Pair(List<Integer> result, int index) { 
      this.result = result; 
      this.index = index; 
     } 

     public List<Integer> getResult() { 
      return result; 
     } 

     public int getIndex() { 
      return index; 
     } 
    } 

    public static void main(String[] args) { 
     List<Integer> items = Arrays.asList(1, 2, 3, 4, 5); 
     foo(items); 
    } 

    private static void foo(List<Integer> items) { 
     Queue<Pair> queue = new LinkedList<Pair>(); 
     queue.add(new Pair(Collections.<Integer>emptyList(), 0)); 

     while (!queue.isEmpty()) { 
      Pair pair = queue.poll(); 

      System.err.println(pair.getResult()); 

      if (pair.getResult().size() < items.size()) { 
       for (int i=pair.getIndex(); i<items.size(); ++i) { 
        List<Integer> copy = new LinkedList<Integer>(pair.getResult()); 
        copy.add(items.get(i)); 
        queue.add(new Pair(copy, i + 1)); 
       } 
      } 
     } 
    } 
} 

Answer 2

La generación de combinaciones lleva MUCHO más tiempo que la clasificación, y no toma tanto tiempo ordenar 100,000 números dado el tiempo de clasificación n*log(n). Estás pre-optimizando. Esto es malo.

Answer 3

Solo haz iterative deepening search.

void comb(int... items) { 
    Arrays.sort(items); 
    for (int k = 1; k <= items.length; k++) { 
     kcomb(items, 0, k, new int[k]); 
    } 
} 
public void kcomb(int[] items, int n, int k, int[] arr) { 
    if (k == 0) { 
     System.out.println(Arrays.toString(arr)); 
    } else { 
     for (int i = n; i <= items.length - k; i++) { 
      arr[arr.length - k] = items[i]; 
      kcomb(items, i + 1, k - 1, arr); 
     } 
    } 
} 

Luego llame, por ejemplo, comb(10,20,30). Se imprimirá:

[10] 
[20] 
[30] 
[10, 20] 
[10, 30] 
[20, 30] 
[10, 20, 30] 

Answer 4

Existen dos formas de interpretar el requisito "ascendente". La interpretación más flexible es "en cada lista, los enteros deben aparecer en orden ascendente". La interpretación más estricta es "las listas deben darse en orden". Supongo que es lo que quieres, pero se me ocurrió una forma iterativa simple de satisfacer el requisito más flexible.

Para n elementos, cuente a través de todos los números de n bits. Si el bit correspondiente a un elemento está allí, entonces está en la lista de resultados.

public static void displaySubsets(List<Integer> sortedInts) { 
    int n=sortedInts.size(); 
    long combinations = 1 << n; 
    for (int setNumber=0; setNumber<combinations; setNumber++) { 
     List<Integer> aResult = new ArrayList<Integer>(); 
     for (int digit=0; digit<n; digit++) { 
     if ((setNumber & (1<<digit)) > 0) { 
      aResult.add(sortedInts.get(digit)); 
     } 
     } 
     System.out.println(aResult.toString()+", "); 
    } 
    } 

Resultado para 1,2,3,4,5 es: [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3 , 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4], [5], [1, 5], [2, 5 ], [1, 2, 5], [3, 5], [1, 3, 5], [2, 3, 5], [1, 2, 3, 5], [4, 5 ], [1, 4, 5], [2, 4, 5], [1, 2, 4, 5], [3, 4, 5], [1, 3, 4, 5] , [2, 3, 4, 5], [1, 2, 3, 4, 5]

Sí, lo sé, pierdo puntos por no usar recursividad.