Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
For first question see here and here –  leonbloy Mar 16 '13 at 0:05

1 Answer 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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.