打印包含3的幂的编号的集合的子集

Question

考虑包含3的幂的编号的集合为{1,3,9,27,....}。现在考虑一个由该集合的子集组成的集合，其名称为{{},{1},{3},{1,3},{9},{1,9},{3,9},{1,3,9}...}

我们应该得到第n个位置的子集，并以递增的顺序打印它的元素，n是输入。

例如:第四个位置的子集(n=4)是{1,3}。此外，n可以是19位数长度。

我被困在弄清楚电力组的顺序上。另外，在java中，apt数据类型会是BigInteger吗？

一组测试用例：

n = 14 op {1,9,27}
n = 783 op {3,9,27,6561,19683}
n = 1125900981634049 op {59049, 3486784401,205891132094649, 717897987691852588770249}

Answer 1

答案很简单。

请注意，数字中出现的位i表示集合中的数字3^i。

因此，您遍历n的位，如果找到位集合，则将3^i添加到集合中。

如果从1开始，然后乘以每个循环的3，则计算3^i很容易。

由此，您应该能够编写代码。

由于位操作的原因，n应该是long IMO类型。3^i应该被视为BigInteger，因为它可以大到3^63。

Answer 2

请注意，在集合{{},{1},{3},{1,3},{9},{1,9},{3,9},{1,3,9}...}中，有一个直接映射到集合中出现的项目，该项目来自列表中的哪个项目。从0进行编号

0 = 0b = {}
1 = 1b = {1}
2 = 10b = {3}
3 = 11b = {1,3}
4 = 100b = {9}
5 = 101b = {1,9}
6 = 110b = {3,9}
7 = 111b = {1,3,9}
8 = 1000b = {27}
....
14 = 1110b
...
783 = 1100001111b
...
1125900981634049 = 100000000000000000001000000000100000000010000000001b

通过这种方式，只需分析序列中集合位置的位模式，就可以确定哪些项目应该出现在集合中。然后，您需要做的就是计算出3对设置的每一位的校正能力。

使用BigInteger是因为它很简单：

List<BigInteger> powerSubSet(long which, int power) {
    // The list I will build and return.
    List<BigInteger> l = new ArrayList<>();
    // A BigInteger version of the power required.
    BigInteger p = BigInteger.valueOf(power);
    // The bit pattern I will inspect.
    BigInteger bits = BigInteger.valueOf(which);
    // Roll each power out of the bit pattern.
    for (int i = bits.bitLength(); i >= 0; i--) {
        // A set bit means yes we want this one.
        if (bits.testBit(i)) {
            l.add(p.pow(i));
        }
    }
    return l;
}

private void test(long i) {
    System.out.println("powerSubSet(" + i + ",3) = " + powerSubSet(i, 3));
}

public void test() {
    test(14);
    test(783);
    test(1125900981634049L);
}

打印

powerSubSet(14,3) = [27, 9, 3]
powerSubSet(783,3) = [19683, 6561, 27, 9, 3, 1]
powerSubSet(1125900981634049,3) = [717897987691852588770249, 205891132094649, 3486784401, 59049, 1]

请注意，您为14设置了{1,9,27}。我得到{3,9,27}，而我们在其他地方是一样的。