I have binary numbers of length s. They are ordered by numbers of ones, and they can have at most j zeros.

That is: first are ordered all numbers containing (s; 0) possible subsets of s numbers, next are all numbers containing (s; 1) possible subsets of s numbers.....last are all (s; j) possible subsets of s numbers.

(s; j) is binomial coefficient s!/(j!(s-j)!)

For s = 4 and j = 2, problem looks like this: 1111 1110 1101 1011 0111 1100 1010 0110 1001 0101 0011

Problem: how can I given the binary representation get the position? 1111 should give me position 0, 1110 should be assigned with position 1, and so on.

Please, I would appreciate any kind of help. Thank you!

  • 1
    $\begingroup$ How are the strings ordered within the group that has the same number of $1$s? Your example is not lexicographic nor by magnitude of the binary (which would be the same order) because 0110 comes before 1001 $\endgroup$ – Ross Millikan Jan 13 '16 at 4:42
  • $\begingroup$ It doesn't matter how are ordered within the group, I can work with any kind of solution, it is just important the order of groups. $\endgroup$ – user3096746 Jan 13 '16 at 4:46
  • $\begingroup$ No, which contest? :) $\endgroup$ – user3096746 Jan 13 '16 at 5:08

The string of all $1$s occupies ${s\choose 0}=1$ positions, so it is in position $0$. The strings with one $0$ occupy ${s \choose 1}=s$ positions, so they run from $1$ to $s$. The strings with two $0$s occupy ${s \choose 2}=\frac 12s(s-1)$ positions from $s+1$ to $s+\frac 12s(s-1)=\frac 12s(s+1)$ and so on. You can just count through the number of zeros and add them up. There is an expression for the cumulative distribution function of the binomial distribution, but it is not simple.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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