Algorytm znajdowania najprostszej kombinacji liczb całkowitych, która nie została jeszcze wykorzystana

Question

Szukam algorytmu do znalezienia najprostszej kombinacji liczb całkowitych od 0 do 5 (czyli tej, która składa się z najmniejszej liczby liczb całkowitych), która ma jeszcze nieużywane (używane kombinacje znajdują się na liście).

Kolejność ma znaczenie, a kombinacje powinny zostać zwrócone na liście.

Na przykład, lista ze stosowanych liczb może wyglądać następująco:

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

W tym przypadku, algorytm powinien zwrócić listę z {5}, ponieważ {5} to kombinacja składająca się z najmniejszej liczby całkowitej.

Jeżeli lista wygląda następująco:

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

algorytm powinien zwrócić listę z 0 i 4 ({0,4}).

Ponieważ ma być używany w Javie, preferowana jest odpowiedź w języku Java, ale można również użyć pseudokodu lub innych języków programowania.

Z góry dziękuję!

Answer 1

Przypuszczam, że przykład 2 jest nieprawidłowy: dla {{0}, {1}, {2}, {3}, {4}, {5}, {0,1}, {0,2}, {0,3}, {0,5}, ...} najmniejszym rozwiązaniem jest {0,0}, {0,4} nie

Kompletne rozwiązania jest tutaj:

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

Po prostu wypróbuj każdą kombinację w kolejności, zaczynając od najkrótszej, i zatrzymaj się, gdy masz taką, która nie jest używana? Czy próbowałeś tego, wydaje się to bardzo oczywiste?

Answer 3

W tym problem, chciałbym stworzyć konkretnego obiektu do przechowywania element (pojedynczy numer lub krotką numer):

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

Kluczem byłby contatenation numerów, nakazał. W twoim przykładzie kluczami będą "0" "1" "2" "3" "4" "5" "01" "02" "03" "05".

Możesz użyć mapy do przechowywania krotek z wartością klucza powiązania.

Ponieważ klawisze respektują porządek logiczny, znalezienie następnej bezpłatnej krotki jest łatwe. Zaczynasz od "0" i zwiększasz klucz (używając zdefiniowanej kolejności), sprawdzasz na mapie, czy nie jest już używana krotka.

W tym przykładzie pierwsza bezpłatna krotka zawiera klawisz "04". Z tego klucza tworzenie skojarzonego krotki jest łatwe.

Answer 4

Kompletny (naiwne) rozwiązanie:

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

wyjściowa:

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

Można prawdopodobnie ją przyspieszyć trochę stosując memoization do przyrostu sposobem.

Answer 5

Jeśli masz uporządkowaną listę, istnieją dwie metody, o których mogę pomyśleć, że są lepsze niż wyszukiwanie liniowe.

Zakładając, że nie wypełnisz całkowicie przestrzeni kombinacji, możesz zastosować odmianę wyszukiwania binarnego.

Po pierwsze, możemy nazwać każdy zestaw wielkości "x" grupą. Tak więc 0,1,2,3,4,5 to grupa 1, {0,0} do {5,5} to grupa 2.

Zaczynając od grupy 1, sprawdź pozycję listy, która zawiera ostatnią wartość w grupie, jeśli wszyscy tam byli. Np. List[5] == 5. Jeśli tak, przejdź do grupy 2 i powtórz. Jeśli nie, przejdź do wyszukiwania binarnego w obrębie tej grupy, zawsze faworyzując niższą stronę, w końcu znajdziesz pierwszą brakującą wartość.

---

W przeciwnym razie można oczekiwać, aby wykorzystać całą przestrzeń skojarzoną ostatecznie, po prostu zrobić binarne wyszukiwania na całej przestrzeni skojarzonego, sprawdzając, czy wartość na pozycji jest zgodna z wartością oczekiwaną, jeśli powyższe wartości wszystkich istniał.