0
$\begingroup$

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!

$\endgroup$
3
  • 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$ Commented Jan 13, 2016 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$ Commented Jan 13, 2016 at 4:46
  • $\begingroup$ No, which contest? :) $\endgroup$ Commented Jan 13, 2016 at 5:08

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.