Find next highest unique number from the given digits

Question

Given a set of n symbols, a size k, and a combination of length k of non-repeating characters from the symbol set, write only an ITERATIVE algorithm to print the next highest unique number that can be made.

Ex:

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

Answer 1

Here's a pseudocode algorithm to do this:

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

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 3

When you are iterating (backwards) across the digits you do not have to check the lowest available every time, instead you can check the last checked digit versus the current, if it is less, skip to the next digit while adding the current to available, if it is more then check the available to find the lowest(higher than current) possible and fill in the rest with lowest from queue.

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

This way you only have to look at the available symbols once, and you are only comparing at most k times.