Algoritmo para encontrar la combinación más simple de enteros que aún no se ha usado

Question

Estoy buscando un algoritmo para encontrar la combinación más simple de enteros de 0 a 5 (que es la que contiene el menor número de enteros) que tiene aún no se ha utilizado (las combinaciones usadas están en una lista).

El orden es importante y las combinaciones se deben devolver en una lista.

Por ejemplo, la lista con los números usados ​​podría tener este aspecto:

{{0}, {1}, {2}, {3}, {4}, {0,0}, {0,1}, {0,2}, ..., {2,1}, {2,2}, ..., {1,5,4}, ...}

En este caso, el algoritmo debería devolver una lista con {5}, ya que {5} es la combinación que consiste en el menor número de enteros.

Si la lista se ve así:

{{0}, {1}, {2}, {3}, {4}, {5}, {0,0}, {0,1 }, {0,2}, {0,3}, {0,5}, ...}

el algoritmo debe devolver una lista con 0 y 4 ({0,4}).

Como se va a utilizar en Java, se prefiere una respuesta de Java, pero también se pueden usar pseudocódigos u otros lenguajes de programación.

¡Gracias de antemano!

Answer 1

Creo que el ejemplo 2 es incorrecto: para {{0}, {1}, {2}, {3}, {4}, {5}, {0,1}, {0,2}, {0,3}, {0,5}, ...} solución más pequeña es {0,0}, {0,4} no

soluciones completas está aquí:

import java.util.*; 

public class Algorithm { 

    static List<List<Integer>> getChildren(List<Integer> node){ 
     List<List<Integer>> children = new ArrayList<List<Integer>>(); 
     for(int i = 0; i < 6; i++){ 
      List<Integer> child = new ArrayList<Integer>(node); 
      child.add(i); 
      children.add(child); 
     } 
     return children; 
    } 

    static List<Integer> find(Queue<List<Integer>> queue, Set<List<Integer>> set){ 

     for(;;){ 
      List<Integer> head = queue.poll(); 
      if(!set.contains(head)){ 
       return head; 
      } else { 
       for(List<Integer> child : getChildren(head)){ 
        queue.add(child); 
       } 
      } 
     } 
    } 

    public static void main(String[] arg) { 
     Queue<List<Integer>> queue = new LinkedList<List<Integer>>(); 
     for(int i = 0; i < 6; i++){ 
      queue.add(Collections.singletonList(i)); 
     } 
     // Example {{0},{1},{2},{3},{4},{5},{0,1},{0,2},{0,3},{0,5},...} 
     Set<List<Integer>> task = new HashSet<List<Integer>>(); 
     task.add(Arrays.asList(0)); 
     task.add(Arrays.asList(1)); 
     task.add(Arrays.asList(2)); 
     task.add(Arrays.asList(3)); 
     task.add(Arrays.asList(4)); 
     task.add(Arrays.asList(5)); 
     task.add(Arrays.asList(0, 1)); 
     task.add(Arrays.asList(0, 2)); 
     task.add(Arrays.asList(0, 3)); 
     task.add(Arrays.asList(0, 5)); 

     System.out.println(find(queue, task)); 
    } 

} 

Answer 2

Simplemente pruebe cada combinación en orden, comenzando con la más corta, y pare cuando tenga una que no se usa? ¿Intentó eso, parece muy obvio de hecho?

Answer 3

para ese problema, crearía un objeto específico para almacenar un elemento (número único o tupla de numer):

class Tuple { 
    String key; 
    Set<Integer> tuple; 
} 

La clave sería el contatenation de los números, clasificadas. En su ejemplo, las claves sería "0" "1" "2" "3" "4" "5" "01" "02" "03" "05".

Puede usar un Mapa para almacenar las tuplas, con la asociación clave-valor.

Dado que las claves respetan un orden lógico, es fácil encontrar la siguiente tupla libre. Simplemente comienza desde "0" e incrementa la clave (usando el orden definido), revisando el Mapa para verificar si la tupla ya está utilizada o no.

En este ejemplo, la primera tupla libre tiene la clave "04". Desde esta clave, crear el Tuple asociado es fácil.

Answer 4

Una solución completa (ingenua):

import java.util.*; 

public class Test { 

    public static String increment(String str) { 
     if (str.isEmpty()) return "0"; 
     int i = str.length() - 1; 
     if (str.charAt(i) < '5') 
      return str.substring(0, i) + (char) (str.charAt(i) + 1); 
     return increment(str.substring(0, i)) + "0"; 
    } 


    public static String nextUnused(Set<String> used) { 
     String s = "0"; 
     while (used.contains(s)) 
      s = increment(s); 
     return s; 
    } 

    public static void main(String args[]) { 
     Set<String> used = new HashSet<String>(Arrays.asList("0", "1", "2", "3", 
       "4", "00", "01", "02", "21", "22", "154")); 
     for (int i = 0; i < 10; i++) { 
      String toUse = nextUnused(used); 
      System.out.println("Adding " + toUse); 
      used.add(toUse); 
     } 
    } 
} 

Salida:

Adding 5 
Adding 03 
Adding 04 
Adding 05 
Adding 10 
Adding 11 
Adding 12 
Adding 13 
Adding 14 
Adding 15 

que probablemente podría acelerarlo un poco aplicando memoization al incremento método.

Answer 5

Si la lista que tiene está ordenada, hay dos métodos que puedo pensar que serían mejores que una búsqueda lineal.

Suponiendo que no va a llenar por completo el espacio de combinación, puede utilizar una variación de una búsqueda binaria.

En primer lugar, vamos a llamar cada conjunto de tamaño 'x' a un grupo. Entonces, 0,1,2,3,4,5 es el grupo 1, {0,0} a {5,5} es el grupo 2.

Comenzando con el grupo 1, verifique la posición de la lista que contiene el último valor en el grupo si todos estaban allí. Por ejemplo, List[5] == 5. Si lo hace, avance al grupo 2 y repita. Si no es así, proceda a hacer una búsqueda binaria dentro de ese grupo, siempre favoreciendo el lado inferior, con el tiempo encontrará el primer valor faltante.

---

De lo contrario si va a utilizar todo el espacio combinación con el tiempo, sólo hacer una búsqueda binaria en todo el espacio de combinación, comprobando si el valor en la posición coincide con el valor esperado si existían los valores anteriores todos.