返回位阵列的第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屋!