用于查找尚未使用的最简单的整数组合的算法

Question

我正在寻找一种算法,用于找到从0到5的整数的最简单组合(即由最少数量的整数组成的整数),这些整数尚未使用(所使用的组合在列表中).

订单确实很重要,组合应该在列表中返回.

例如,使用过的数字的列表可能如下所示:

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

在这种情况下,算法应该返回一个{5}的列表,因为{5}是由最少的整数组成的组合.

如果列表如下所示:

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

算法应该返回一个0和4({0,4})的列表.

由于它将在Java中使用,因此Java答案是可取的,但伪代码或其他编程语言也是可用的.

先感谢您!

Answer 1

我猜示例 2 是错误的：对于 {{0},{1},{2},{3},{4},{5},{0,1},{0,2},{0,3} ,{0,5},...} 最小解是 {0,0}，而不是 {0,4}

完整的解决方案在这里：

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

}