Algorithme pour trouver la combinaison la plus simple de nombres entiers qui n'a pas encore été utilisée

Question

Je cherche un algorithme pour trouver la combinaison la plus simple d'entiers de 0 à 5 (c'est-à-dire le nombre le plus petit d'entiers) qui a pas encore utilisé (les combinaisons utilisées sont dans une liste).

L'ordre est important et les combinaisons doivent être renvoyées dans une liste.

Par exemple, la liste des numéros utilisés pourrait ressembler à ceci:

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

Dans ce cas, l'algorithme doit renvoyer une liste avec {5}, car {5} est la combinaison qui contient le moins d'entiers.

Si la liste ressemble à ceci:

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

l'algorithme devrait retourner une liste avec 0 et 4 ({0,4}).

Comme il doit être utilisé en Java, une réponse Java est préférable mais le pseudo-code ou d'autres langages de programmation sont également utilisables.

Merci d'avance!

Answer 1

Je suppose que l'exemple 2 est faux: pour {{0}, {1}, {2}, {3}, {4}, {5}, {0,1}, {0,2}, {0,3}, {0,5}, ...} est la plus petite solution {0,0}, {pas} 0,4

solutions complètes sont ici:

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

Essayez simplement chaque combinaison dans l'ordre, en commençant par la plus courte, et arrêtez quand vous en avez une qui n'est pas utilisée? Avez-vous essayé cela, il semble très évident en effet?

Answer 3

Pour ce problème, je voudrais créer un objet spécifique pour stocker un élément (numéro unique ou tuple de numer):

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

La clé serait la contatenation des numéros, commandés. Dans votre exemple, les touches seraient "0" "1" "2" "3" "4" "5" "01" "02" "03" "05".

Vous pouvez utiliser une carte pour stocker les tuples, avec la clé-valeur d'association. Comme les clés respectent un ordre logique, trouver le prochain tuple libre est facile. Vous commencez simplement à partir de "0" et incrémentez la clé (en utilisant l'ordre défini), en vérifiant dans la carte pour vérifier si le tuple est déjà utilisé ou non.

Dans cet exemple, le premier tuple libre a la touche "04". A partir de cette clé, créer le Tuple associé est facile.

Answer 4

Une complète (naïve) solution:

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); 
     } 
    } 
} 

Sortie:

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

Vous pourriez probablement accélérer tout à fait un peu en appliquant memoization à la méthode d'augmentation.

Answer 5

Si la liste que vous avez est ordonnée, il y a 2 méthodes que je peux penser qui serait mieux qu'une recherche linéaire.

En supposant que vous ne remplissez pas complètement l'espace de combinaison, vous pouvez utiliser une variation d'une recherche binaire.

D'abord, appelons chaque groupe de taille 'x' un groupe. Donc, 0,1,2,3,4,5 est le groupe 1, {0,0} à {5,5} est le groupe 2.

À partir du groupe 1, vérifiez la position de la liste qui contient la dernière valeur dans le groupe s'ils étaient tous là. Par exemple, List[5] == 5. Si c'est le cas, passez au groupe 2 et répétez. Si ce n'est pas le cas, continuez à faire une recherche binaire dans ce groupe en privilégiant toujours le côté inférieur, vous trouverez éventuellement la première valeur manquante.

---

Sinon, si vous prévoyez d'utiliser tout l'espace de combinaison éventuellement, faire juste une recherche binaire sur l'ensemble de l'espace de combinaison, de vérifier si la valeur à la position correspond à la valeur attendue si les valeurs précédentes tous existaient.