CODEWITHSUNDEEP
algorithmbitcombinatoricssequencescomputation
Eduard
Eduard

Reputation: 127

Quick way to compute n-th sequence of bits of size b with k bits set?

I want to develop a way to be able to represent all combinations of b bits with k bits set (equal to 1). It needs to be a way that given an index, can get quickly the binary sequence related, and the other way around too. For instance, the tradicional approach which I thought would be to generate the numbers in order, like: For b=4 and k=2:

0- 0011

1- 0101

2- 0110

3- 1001

4-1010

5-1100

If I am given the sequence '1010', I want to be able to quickly generate the number 4 as a response, and if I give the number 4, I want to be able to quickly generate the sequence '1010'. However I can't figure out a way to do these things without having to generate all the sequences that come before (or after). It is not necessary to generate the sequences in that order, you could do 0-1001, 1-0110, 2-0011 and so on, but there has to be no repetition between 0 and the (combination of b choose k) - 1 and all sequences have to be represented.

How would you approach this? Is there a better algorithm than the one I'm using?

Upvotes: 4

Views: 184

Answers (1)

kevmo314
kevmo314

Reputation: 4317

pkpnd's suggestion is on the right track, essentially process one digit at a time and if it's a 1, count the number of options that exist below it via standard combinatorics.

nCr() can be replaced by a table precomputation requiring O(n^2) storage/time. There may be another property you can exploit to reduce the number of nCr's you need to store by leveraging the absorption property along with the standard recursive formula.

Even with 1000's of bits, that table shouldn't be intractably large. Storing the answer also shouldn't be too bad, as 2^1000 is ~300 digits. If you meant hundreds of thousands, then that would be a different question. :)

import math

def nCr(n,r):
    return math.factorial(n) //  math.factorial(r) //  math.factorial(n-r)

def get_index(value):
  b = len(value)
  k = sum(c == '1' for c in value)
  count = 0
  for digit in value:
    b -= 1
    if digit == '1':
      if b >= k:
        count += nCr(b, k)
      k -= 1
  return count

print(get_index('0011')) # 0
print(get_index('0101')) # 1
print(get_index('0110')) # 2
print(get_index('1001')) # 3
print(get_index('1010')) # 4
print(get_index('1100')) # 5

Nice question, btw.

Upvotes: 3

Related Questions