0

intすべての包含0,1,2,2,4,4(またはlongセットが大きい場合は s)を生成したい。桁数が少ない場合は、手作業で簡単に実行できますが、どうすればそれができるのかわかりません。

私のサンプルのようにそれほど大きくない整数のセットの場合、次のようなものを使用できます。

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

しかし、ご覧のとおり、より大きなセットの場合、複雑さは私たちができる最高のものとはほど遠いものです (O(10 n )、しかし私は間違っているかもしれません)。これを行う方法について何かヒントはありますか?

サンプルは宿題ではなくランダムに選ばれます!

これは私の解決策ですが、実際には膨大な数に最適化されているわけではありませんが、一部の人々を助けるかもしれません:

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

2 に答える 2