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

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

对于{{0}，{1}，{2}，{3}，{4}，{5}，{0,1}，{0,2}，我猜想示例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

只要按顺序尝试每个组合，从最短开始，并停止当你有一个不使用？你有没有尝试过，看起来非常明显？

Answer 3

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

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

的关键将是数字的contatenation，排序。 在你的例子中，键将是“0”“1”“2”“3”“4”“5”“01”“02”“03”“05”。

您可以使用Map来存储具有关联键值的元组。

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

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

Answer 4

一个完整的（幼稚）解决方案：

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 5

如果您已经订购了该列表，那么有两种方法我可以认为这比线性搜索更好。

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

首先，让我们调用每一组大小'x'。因此，0,1,2,3,4,5是组1，{0,0}到{5,5}是组2.从组1开始，检查包含最后一个值的列表位置如果他们都在那里的话。例如，List[5] == 5。如果确实如此，请转到第2组并重复。如果没有，继续在该组中进行二分搜索，总是偏向低端，最终会找到第一个缺失的值。

---

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