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

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

}

Answer 2

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.