返回位阵列的第i个组合 [英] Returning i-th combination of a bit array

问题描述

由于固定长度的0和1包含的数位阵列，我怎么可以安排所有可能的组合，使得返回第i个组合需要尽可能少的时间呢？ 它并不重要它们被返回的顺序。

Given a bit array of fixed length and the number of 0s and 1s it contains, how can I arrange all possible combinations such that returning the i-th combinations takes the least possible time? It is not important the order in which they are returned.

下面是一个例子：

array length = 6
number of 0s = 4
number of 1s = 2

可能的组合（6！/ 4！/ 2！）     000011 000101 000110 001001 001010     001100 010001 010010 010100 011000     100001 100010 100100 101000 110000

possible combinations (6! / 4! / 2!) 000011 000101 000110 001001 001010 001100 010001 010010 010100 011000 100001 100010 100100 101000 110000

问题     第一组合= 000011     5组合= 001010     9日联合= 010100

problem 1st combination = 000011 5th combination = 001010 9th combination = 010100

通过不同的安排，如     100001 100010 100100 101000 110000     001100 010001 010010 010100 011000     000011 000101 000110 001001 001010

With a different arrangement such as 100001 100010 100100 101000 110000 001100 010001 010010 010100 011000 000011 000101 000110 001001 001010

它应返回     第一组合= 100001     5组合= 110000     9日联合= 010100

it shall return 1st combination = 100001 5th combination = 110000 9th combination = 010100

目前我使用的是O（n）的算法测试对于每一位无论是1或0。问题是我需要处理很多很长的阵列（在10000位的顺序），因此它仍然很慢（和缓存是不可能的）。我想知道，如果你想更快的算法可能存在。

Currently I am using a O(n) algorithm which tests for each bit whether it is a 1 or 0. The problem is I need to handle lots of very long arrays (in the order of 10000 bits), and so it is still very slow (and caching is out of the question). I would like to know if you think a faster algorithm may exist.

感谢您

推荐答案

我不知道我理解的问题，但如果你只想要第i个组合，而不会产生其他的，这里是一个可能的算法：

I'm not sure I understand the problem, but if you only want the i-th combination without generating the others, here is a possible algorithm:

有C（M，N）= M！/（N！（MN）！）N位的组合设置为1，最多最高位具有位置M。

There are C(M,N)=M!/(N!(M-N)!) combinations of N bits set to 1 having at most highest bit at position M.

您想第i：你反复增加M键直至C（M，N）> = I

You want the i-th: you iteratively increment M until C(M,N)>=i

while( C(M,N) < i ) M = M + 1

这将告诉你所设置的最高位。 当然，你反复地与计算相结合

That will tell you the highest bit that is set. Of course, you compute the combination iteratively with

C(M+1,N) = C(M,N)*(M+1)/(M+1-N)

一旦发现，你有找到（IC（M-1，N））第N-1位的组合，这样你就可以递归的N申请的问题...
这里是一个可能的变型为D = C（M + 1，N）-C（M，N），并且I = I-1，使其开始在零

Once found, you have a problem of finding (i-C(M-1,N))th combination of N-1 bits, so you can apply a recursion in N...
Here is a possible variant with D=C(M+1,N)-C(M,N), and I=I-1 to make it start at zero

SOL=0
I=I-1
while(N>0)
    M=N
    C=1
    D=1
    while(i>=D)
        i=i-D
        M=M+1
        D=N*C/(M-N)
        C=C+D
    SOL=SOL+(1<<(M-1))
    N=N-1
RETURN SOL

这将需要大量的整数运算，如果你有很多位...

This will require large integer arithmetic if you have that many bits...

这篇关于返回位阵列的第i个组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！