Algorithm to find the simplest combination of integers that has not yet been used

Question

I am looking for an algorithm for finding the simplest combination of integers from 0 to 5 (that is the one that consists of the fewest number of integers) that has not yet been used (the used combinations are in a list).

The order does matter and the combinations should be returned in a list.

For example, the list with the used numbers could look like this:

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

In this case, the algorithm should return a list with {5}, as {5} is the combination that consists of the fewest integers.

If the list looks like this:

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

the algorithm should return a list with 0 and 4 ({0,4}).

As it is to be used in Java, a Java answer is preferable but pseudo-code or other programming languages are usable too.

Thank you in advance!

Answer 1

Just try each combination in order, starting with the shortest, and stop when you have one which isn't used? Did you try that, it seems very obvious indeed?

Answer 2

For that problem, I would create a specific object to store an element (single number or tuple of numer) :

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

The key would be the contatenation of the numbers, ordered. In your example, the keys would be "0" "1" "2" "3" "4" "5" "01" "02" "03" "05".

You can use a Map to store the tuples, with the association key - value.

Since the keys respect a logical order, finding the next free tuple is easy. You just start from "0" and increment the key (using the defined order), checking in the Map to verify if the tuple is already used or not.

In this example, the first free tuple has the key "04". From this key, creating the associated Tuple is easy.

Answer 3

A complete (naive) solution:

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

Output:

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

You could probably speed it up quite a bit by applying memoization to the increment-method.

Answer 4

If the list you have is ordered, there are 2 methods I can think of that would be better than a linear search.

Assuming that you will not completely fill the combination space, you can use a variation of a binary search.

First, lets call each set of size 'x' a group. So, 0,1,2,3,4,5 is group 1, {0,0} to {5,5} is group 2.

Starting with group 1, check the list position that contain the last value in the group if they were all there. Eg, List[5] == 5. If it does, move on to group 2 and repeat. If it doesn't, proceed to do a binary search within just that group always favoring the lower side, eventually you will find the first missing value.

---

Otherwise if you expect to use the entire combination space eventually, just do a binary search on the entire combination space, checking if the value at the position matches the expected value if the preceding values all existed.

Answer 5

I guess example 2 is wrong: for {{0},{1},{2},{3},{4},{5},{0,1},{0,2},{0,3},{0,5},...} smallest solution is {0,0}, not {0,4}

Complete solutions is here:

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

}