java - 如何用一组数字生成每个整数？

Question

我想生成每个 int 包含 0,1,2,2,4,4(或者 long，如果集合是大)。对于少量数字，手工很容易实现，但我不明白我该怎么做。

对于不太大的整数集，比如我的示例，我们可以使用类似的东西:

for(i = 102244; i <= 442210; i++){
   //check if the digits are in the number
   //add it to a tree
}

但如您所见，对于更大的集合，其复杂度远非我们所能做到的最好(O(10ⁿ)，但我可能是错的)。您对如何执行此操作有任何提示吗？

样本是随机选择的，不是作业!

这是我的解决方案，但它并没有真正针对大量数据进行优化，不过可能会对某些人有所帮助:

@Test
public void testPossibleNumbers(){
    TreeSet<Long> possibleNumbers = new TreeSet<Long>();
    String a = "012244";
    permutation("",a,possibleNumbers);
    LOGGER.info("Array of possible numbers"); //breapoint: 150 solutions
}

private static void permutation(String prefix, String str, TreeSet<Long> tree) {
    int n = str.length();
    if (n == 0 && !prefix.startsWith("0")){
        tree.add(Long.parseLong(prefix));
    }
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), tree);
    }
}

Answer 1

您只需枚举起始“集合”的所有排列(它实际上不是一个集合，它包含重复项)。当然，您最终可能会得到一些重复项(因为您不是从集合开始的)并且数字以(任意数量的)0 (es) 开头，您应该考虑到这一点。

我会做的是使用某种不接受重复的容器(std::set in c++)，然后开始使用排列在其中推送数字，如 012244 012244 012424 012442 ... 442210

容器会考虑重复项，零“问题”不会成为问题，因为 0*10^5+1*10^4+...+2 不会跟踪前导“0”。