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

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

}

Answer 2

如果您的列表是有序的，我可以想到两种比线性搜索更好的方法。

假设您不会完全填满组合空间，则可以使用二分搜索的变体。

首先，我们将每组大小为“x”的组称为一组。因此，0,1,2,3,4,5 是组 1，{0,0} 到 {5,5} 是组 2。

从组 1 开始，检查包含组中最后一个值的列表位置，如果他们都在那里。例如，List[5] == 5。如果是这样，请转到第 2 组并重复。如果没有，则继续在该组内进行二分搜索，始终倾向于较低的一侧，最终您将找到第一个缺失值。

---

否则，如果您希望最终使用整个组合空间，只需对整个组合空间进行二分搜索，如果前面的值都存在，则检查该位置的值是否与预期值匹配。

Answer 3

一个完整的（天真的）解决方案：

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

输出：

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

您可以通过应用 memoization 来加快速度 到增量方法。

Answer 4

只需按顺序尝试每种组合，从最短的开始，当有一个未使用时停止？你尝试过吗，这看起来确实很明显吗？

Answer 5

对于这个问题，我将创建一个特定的对象来存储一个元素（单个数字或数字元组）：

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

关键是数字的串联，有序。
在您的示例中，键将为“0”“1”“2”“3”“4”“5”“01”“02”“03”“05”。

您可以使用 Map 来存储元组，并使用关联键 - 值。

由于键遵循逻辑顺序，因此找到下一个自由元组很容易。您只需从“0”开始并递增键（使用定义的顺序），检查映射以验证元组是否已使用。

在此示例中，第一个空闲元组的键为“04”。通过这个键，创建关联的元组很容易。