Trova il numero univoco più alto successivo dalle cifre fornite

Question

Dato un insieme di n simboli, una dimensione k e una combinazione di lunghezza k di caratteri non ripetuti dal set di simboli, scrivere solo un algoritmo ITERATIVO per stampare il successivo valore più alto univoco numero che può essere fatto.

Es:

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

Answer 1

Ecco un algoritmo di pseudocodice per fare questo:

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

provare questo metodo fuori:

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

Quando si effettua l'iterazione (indietro) attraverso le cifre non è necessario controllare il più basso disponibile ogni volta, invece è possibile controllare l'ultima cifra controllata rispetto alla corrente, se è inferiore, saltare alla cifra successiva mentre si aggiunge la corrente a disponibile, se è più quindi controllare la disponibilità per trovare la più bassa (superiore a quella attuale) possibile e riempire il resto con il più basso dalla coda.

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 

In questo modo è sufficiente guardare i simboli disponibili una sola volta e si stanno confrontando al massimo k volte.