1

I first enumerate a list of all possible binary strings for a length $n$ (e.g., ["00", "01", "10", "11"] for $n=4$). This leads to a list of $2^n$ binary strings. Within that list of $2^n$ elements, I'm principally interested in the $C_k^n$ combinations of strings, for example all binary strings with a single bit set to $1$ ($k = 1$, or ["01", "10"] in the above case).

Now, how can I do the following two things (the first is really an efficiency question, the second I do not know how to do):

  1. Determine if a string has $k$ ones in it (based on the integer value of the binary string vs. simply counting the occurrences of "1")

  2. For a given string / binary value, determine it's position within the subset of all possible strings of $n$-length and with $k$-ones. For example, for an enumeration of all strings where $n=2$ and $k=1$ – ["00", "01", "10", "11"] – I would like to calculate that "01" appears first while "10" appears second).

    Note: I realize this will depend on how the $C_k^n$ combinations are enumerated (["01", "10"] vs. ["10", "01"]) and am also open to suggestions on the best enumeration method to use).

Many thanks for the help,

Ryan

Ryan
  • 11

1 Answers1

1

As explained under combinatorial number system the number (starting from $0$) you want to associate to the bit string with $k$ raised bits in postions $c_1,\ldots,c_k$ (also counting from $0$, so the bit at postion $c_i$ represents $2^{c_i}$) is $$ \binom{c_1}1+\binom{c_2}2+\cdots+\binom{c_k}k. $$ (Note that for the smallest possibility, with $c_i=i-1$ for $i=1,2,\ldots,k$, all terms are $0$.) This number gives the position of the number $2^{c_k}+\cdots+2^{c_2}+2^{c_1}$ among all numbers whose binary representations have exactly $k$ bits equal to $1$.

Marc van Leeuwen
  • 115,048