Encontrar el siguiente número único más alto de los dígitos dados

Question

Dado un conjunto de n símbolos, un tamaño k y una combinación de longitud k de caracteres no repetitivos del conjunto de símbolos, escriba solo un algoritmo ITERATIVE para imprimir el siguiente máximo único número que se puede hacer.

Ex:

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

Answer 1

He aquí un algoritmo de pseudocódigo para hacer esto:

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

Pruebe este método a cabo:

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

Cuando está iterando (hacia atrás) a través de los dígitos no es necesario comprobar el más bajo disponible en todo momento, en su lugar puede verificar el último dígito marcado versus el actual, si es menor, salte al siguiente dígito mientras agrega la corriente a disponible; si es más, luego marque la disponible para encontrar la más baja (más alta que la actual) posible y complete el resto con el más bajo de la cola.

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 

De esta manera solo tiene que mirar los símbolos disponibles una vez, y solo está comparando a lo sumo k veces.