Znajdź następny najwyższy unikalny numer z podanych cyfr

Question

Biorąc pod uwagę zestaw n symboli, rozmiar k, oraz kombinację długości k nie powtarzających się znaków ze zbioru symboli, napisz tylko algorytm ITERATYWNY, aby wydrukować następny najwyższy unikat numer, który można wykonać.

Ex:

Symbols =[1,2,3,4,5] 
size = 3; 
given combination = 123, result = 124 
given combination = 254, result = 312 

Answer 1

Oto algorytm pseudokod, aby to zrobić:

int n = length(Symbols); 
int k = length(A); 
// TRACK WHICH LETTERS ARE STILL AVAILABLE 
available = sort(Symbols minus A); 
// SEARCH BACKWARDS FOR AN ENTRY THAT CAN BE INCREASED 
for (int i=k-1; i>=0; --i) { 
    // LOOK FOR NEXT SMALLEST AVAILABLE LETTER 
    for (int j=0; j<n-k; ++j) { 
     if (A[i] < available[j]) { 
      break; 
     } 
    } 
    if (j < n-k) { 
     // CHANGE A[i] TO THAT, REMOVE IT FROM AVAILABLE 
     int tmp = A[i]; 
     A[i] = available[j]; 
     available[j] = tmp; 
     // RESET SUBSEQUENT ENTRIES TO SMALLEST AVAILABLE 
     for (j=i+1; i<k; ++j) { 
      A[j] = available[i+1-j]; 
     } 
     return A; 
    } else { 
     // A[i] MUST BE LARGER THAN AVAILABLE, SO APPEND TO END 
     available = append(available,A[i]); 
    } 
} 

Answer 2

Spróbuj tej metody out:

public int nextCombo(int[] symbols, int combo, int size) { 
    String nc = ""; 
    symbols = java.util.Arrays.sort(symbols); 
    for (int i = 0; i < size; i++) nc += Integer.toString(symbols[symbols.length - 1]); 
    if (Integer.parseInt(nc) == combo) return combo; //provided combo is the largest possible so end the method 
    nc = ""; 
    int newCombo = 0; 
    while (newCombo < combo) { //repeat this process until the new combination is greater than the provided one 
     for (int i = 0; i < size; i++) { //keep appending numbers from the symbol array onto the new combo until the size limit is reached 
      nc += Integer.toString(symbols[(int) Math.floor(Math.random() * size)]); 
     } 
     newCombo = Integer.parseInt(nc); 
    } 
    return newCombo; 
} 

Answer 3

public class IncrementSybmols { 
    public static void main(String[] args) throws Throwable { 
     List<Integer> syms = Arrays.asList(1,2,3,4,5); 

     test(syms, 3, Arrays.asList(1,2,3), Arrays.asList(1,2,4)); 
     test(syms, 3, Arrays.asList(2,5,4), Arrays.asList(3,1,2)); 

     test(syms, 3, Arrays.asList(4,3,5), Arrays.asList(4,5,1)); 
     test(syms, 3, Arrays.asList(5,4,2), Arrays.asList(5,4,3)); 
     test(syms, 3, Arrays.asList(5,4,3), null); 
    } 

    private static void test(List<Integer> syms, int n, List<Integer> in, List<Integer> exp) { 
     List<Integer> out = increment(syms, n, in); 
     System.out.println(in+" -> "+out+": "+(exp==out || exp.equals(out)?"OK":"FAIL")); 
    } 

    private static List<Integer> increment(List<Integer> allSyms, int n, List<Integer> in){ 
     TreeSet<Integer> availableSym = new TreeSet<Integer>(allSyms); 
     availableSym.removeAll(in); 

     LinkedList<Integer> current = new LinkedList<Integer>(in); 

     // Remove symbols beginning from the tail until a better/greater symbols is available. 
     while(!current.isEmpty()){ 
      Integer last = current.removeLast(); 
      availableSym.add(last); 

      // look for greater symbols 
      Integer next = availableSym.higher(last); 
      if(next != null){ 
       // if there is a greater symbols, append it 
       current.add(next); 
       availableSym.remove(next); 
       break; 
      } 
     } 

     // if there no greater symbol, then *shrug* there is no greater number 
     if(current.isEmpty()) 
      return null; 

     // fill up with smallest symbols again 
     while(current.size() < n){ 
      Integer next = availableSym.first(); 
      availableSym.remove(next); 
      current.add(next); 
     } 

     return current; 
    } 
} 

Answer 4

Kiedy iteracja (do tyłu) przez cyfry nie musisz sprawdzać najniższego dostępne za każdym razem, zamiast tego możesz sprawdzić ostatnią zaznaczoną cyfrę w porównaniu z bieżącą, jeśli jest mniejsza, przejdź do następnej cyfry dodając aktualny do dostępnego, jeśli jest więcej niż sprawdź dostępne, aby znaleźć najniższą (wyższą niż obecna) możliwe i wypełnić resztę najniższą z kolejki.

i.e. 254 

current = 4  // 4 < 1,3 so no higher available 
last_checked = 4 // available = {1, 3, 4} 
current = 5  // 4 < 5 so no higher available 
last_checked = 5 // available = {1, 3, 4, 5} 
current = 2  // 5 > 2 so search available for lowest possible(higher than 2) = 3 
set 3,_,_  // Then just add lowest elements until full: 3,1,2 = 312 

W ten sposób wystarczy spojrzeć na dostępne symbole tylko raz, a porównuje się je najwyżej k razy.