查找具有 10 个设置位的第 n 个整数

Question

找到第 n 个具有 10 个设置位的整数
n 是 0<= n <= 30 045 014
范围内的整数第 0 个 int = 1023，第 1 个 = 1535 等等

snob() 位数相同，
returns 大于 n 且设置位数与 n 相同的最小整数

int snob(int n) {
    int a=n&-n, b=a+n;
    return b|(n^b)/a>>2;
  }

调用 snob n 次即可

int nth(int n){
int o =1023;
for(int i=0;i<n;i++)o=snob(o);
return o;
}

示例

https://ideone.com/ikGNo7

有什么方法可以更快地找到它吗？

我找到了一种模式，但不确定它是否有用。

使用阶乘，您可以找到 "indexes"，其中所有 10 个设置位都是连续的

1023 << x = the (x+10)! / (x! * 10!) - 1 th integer

1023<<1 is the 10th  
1023<<2 is the 65th  
1023<<3 the 285th  
...

顺便说一句，我不是学生，这不是作业。

编辑：

找到了 snob() 的替代方法

https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

int lnbp(int v){
 int t = (v | (v - 1)) + 1;  
 return t | ((((t & -t) / (v & -v)) >> 1) - 1);  
}

Answer 1

让我们考虑设置了 k=10 位的数字。

诀窍是针对给定的 n 确定最重要的排名。

有一个长度为k的数：C(k, k)=1。有 k+1 = C(k+1, k) 个长度为 k + 1 的数字。 ... 有 C(m, k) 个长度为 m 的数字。

对于k=10，极限n为1 + 10 + 55 + 220 + 715 + 2002 + 5005 + 11440 + ...

对于给定的n，你很容易找到对应的m。然后问题简化为找到第 n - C(m, k) 个具有 k - 1 位集的数字。以此类推。

使用预先计算的表格，这会非常快。 30045015 需要 30 次查找，所以我猜最坏的情况是 29 x 30 / 2 = 435 次查找。

（这是基于线性查找，以支持较小的值。通过二分法搜索，您可以将其减少到小于 29 x lg(30) = 145 次查找，更糟糕的是。）

更新：

我之前的估计是悲观的。事实上，由于我们正在寻找 k 位，因此只有 10 个确定的 m。在线性情况下，更糟糕的是 245 次查找，在二分法情况下，少于 50.

（我不排除估计中的差一错误，但显然这种方法非常有效并且不需要势利。）

Answer 2

我已经构建了一个可以满足您需求的实现。

/** A lookup table to see how many combinations preceeded this one */
private static int[][] LOOKUP_TABLE_COMBINATION_POS;
/** The number of possible combinations with i bits */
private static int[] NBR_COMBINATIONS;
static {
    LOOKUP_TABLE_COMBINATION_POS = new int[Integer.SIZE][Integer.SIZE];
    for (int bit = 0; bit < Integer.SIZE; bit++) {
        // Ignore less significant bits, compute how many combinations have to be
        // visited to set this bit, i.e.
        // (bit = 4, pos = 5), before came 0b1XXX and 0b1XXXX, that's C(3, 3) + C(4, 3)
        int nbrBefore = 0;
        // The nth-bit can be only encountered after pos n
        for (int pos = bit; pos < Integer.SIZE; pos++) {
            LOOKUP_TABLE_COMBINATION_POS[bit][pos] = nbrBefore;
            nbrBefore += nChooseK(pos, bit);
        }
    }
    NBR_COMBINATIONS = new int[Integer.SIZE + 1];
    for (int bits = 0; bits < NBR_COMBINATIONS.length; bits++) {
        NBR_COMBINATIONS[bits] = nChooseK(Integer.SIZE, bits);
        assert NBR_COMBINATIONS[bits] > 0; // Important for modulo check. Otherwise we must use unsigned arithmetic
    }
}

private static int nChooseK(int n, int k) {
    assert k >= 0 && k <= n;
    if (k > n / 2) {
        k = n - k;
    }
    long nCk = 1; // (N choose 0)
    for (int i = 0; i < k; i++) {
        // (N choose K+1) = (N choose K) * (n-k) / (k+1);
        nCk *= (n - i);
        nCk /= (i + 1);
    }
    return (int) nCk;
}

public static int nextCombination(int w, int n) {
    // TODO: maybe for small n just advance naively

    // Get the position of the current pattern w
    int nbrBits = 0;
    int position = 0;
    while (w != 0) {
        final int currentBit = Integer.lowestOneBit(w); // w & -w;
        final int bitPos = Integer.numberOfTrailingZeros(currentBit);
        position += LOOKUP_TABLE_COMBINATION_POS[nbrBits][bitPos];
        // toggle off bit
        w ^= currentBit;
        nbrBits++;
    }

    position += n;
    // Wrapping, optional
    position %= NBR_COMBINATIONS[nbrBits];

    // And reverse lookup
    int v = 0;
    int m = Integer.SIZE - 1;
    while (nbrBits-- > 0) {
        final int[] bitPositions = LOOKUP_TABLE_COMBINATION_POS[nbrBits];
        // Search for largest bitPos such that position >= bitPositions[bitPos]
        while (Integer.compareUnsigned(position, bitPositions[m]) < 0)
            m--;
        position -= bitPositions[m];
        v ^= (0b1 << m--);
    }
    return v;
}

现在进行一些解释。 LOOKUP_TABLE_COMBINATION_POS[bit][pos] 是算法的核心，使它尽可能快。 table 的设计使得在位置 p_0 < p_1 < ... < p_{k - 1} 处具有 k 位的位模式的位置为 `\sum_{i = 0}^{k - 1}{ LOOKUP_TABLE_COMBINATION_POS[i][p_i] }.

直觉是我们尝试将位一位一位地移回，直到我们达到所有位都位于最低可能位置的模式。将第 i 位从位置 k + 1 移动到 k 向后移动 C(k-1, i-1) 个位置，前提是所有低位都在最右边的位置（没有移动位进入或通过彼此）因为我们跳过了所有可能的组合 k-1 槽中的 i-1 位。

因此我们可以 "decode" 一个位置的位模式，跟踪遇到的位。然后我们前进 n 个位置（如果我们为 k 位枚举所有可能的位置则滚动）并再次编码该位置。

为了对模式进行编码，我们将这个过程颠倒过来。为此，我们将位从它们的起始位置向前移动，只要该位置小于我们的目标。我们可以不通过 LOOKUP_TABLE_COMBINATION_POS 进行线性搜索，而是对我们的目标索引 m 使用二进制搜索，但这几乎不需要，int 的大小并不大。然而，我们重用我们的变体，即较小的位也必须出现在不太重要的位置，因此我们的算法实际上是 O(n) where n = Integer.SIZE.

我仍然使用以下断言来展示生成的算法：

nextCombination(0b1111111111,  1) == 0b10111111111;
nextCombination(0b1111111111, 10) == 0b11111111110;
nextCombination(0x00FF      ,  4) == 0x01EF;
nextCombination(0x7FFFFFFF  ,  4) == 0xF7FFFFFF;
nextCombination(0x03FF      , 10) == 0x07FE;
// Correct wrapping
nextCombination(0b1         , 32) == 0b1;
nextCombination(0x7FFFFFFF  , 32) == 0x7FFFFFFF;
nextCombination(0xFFFFFFEF  ,  5) == 0x7FFFFFFF;

查找具有 10 个设置位的第 n 个整数

Find nth int with 10 set bits

optimization

combinatorics