寻找最简整数组合的算法，该组合尚未被使用过。

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 答案，但伪代码或其他编程语言也可用。

提前致谢！

- akaloer

---

{0,1,2, ... 应该改为 {{0},{1},{2}, ... - aioobe

+1 给了我早餐时可以思考的东西 ;) - aioobe

你是那个使用返回值填写列表的人吗？那么，首先返回所有长度为1的组合，然后是长度为2的组合，以此类推。 - Fakrudeen

@akaloer 我和Fakrudeen有同样的问题。列表是从哪里来的？如果你创建它，那就枚举集合{1,2,3,4,5}的所有子集。 - Dave O.

是的，我自己创建了这个列表。 - akaloer

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

}

- Nulldevice

---

其实不是我发现的——是我写的程序发现的 :) - Nulldevice

Answer 2

如果你的列表是有序的，那么有两种比线性搜索更好的方法。

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

首先，让我们把每个大小为“x”的集合称为一组。所以，0,1,2,3,4,5是第一组，{0,0}到{5,5}是第二组。

从第一组开始，检查包含该组中所有值的最后一个值的列表位置。例如，List[5] == 5。如果是这样，就继续进行第二组并重复。如果不是，则在该组内进行二分搜索，始终优先选择较低的一侧，最终你将找到第一个缺失的值。

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

- Dan McGrath

---

这里我指出你描述中的不一致之处。你排除了{0,0}，但包括{2,2}。{0,0}也是一个可能的解决方案。在我的例子中，{0,0}没有被使用，因此它不在列表中。 - akaloer

假设输入已经排序，第二种方法似乎是非常好的（可能是最优的）方案。 - Eyal Schneider

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

你可以通过将记忆化应用于增量方法来加快速度。

- aioobe

Answer 4

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

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

关键是按顺序连接数字。 在您的示例中，关键字将是“0”“1”“2”“3”“4”“5”“01”“02”“03”“05”。

您可以使用Map来存储元组及其关联的键值对。

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

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

- Benoit Courtine

Answer 5

按顺序尝试每种组合，从最短的开始，直到找到一个未使用的组合为止？你试过了吗？这似乎非常显然。

- Kieren Johnstone