1
$\begingroup$

Suppose a number is given = $5$ then from the number how to formulate the series -

$1, 2, 4, 8, 16, 3, 5, 9, 17, 6, 10, 18, 12, 20, 24, 7, 13, 21, 11, 19, ...$

actually I want a function of n and the given number m (5 in this case) such that f(1)=1, $f(2) = 2, f(3)=4 ... f(6)=3, f(7) = 5$ like this

Background of the problem : I faced a situation where I needed to find out all possible combination of $5$ digit binary number in a specific order like - $1,10,100,1000,10000,11,101,1001,10001 ....$ i.e. all possible combination of one 1 digit in the $5$ digit precedes all possible combination of two $1$ digit in $5$ digit combination (if possible in the order too) so on

Any solution? thanks in advance

  • 0
    @GerryMyerson +1 Though the in$f$ormation is very use$f$ul, but does not quite solve my problem2012-11-02

1 Answers 1

3

I developed this formulation for the problem, for simplification i ranked the numbers in a decreasing fashion (within a set of numbers with a fixed number of digits set to one) as I didn't get how the local rank mechanism of the original post worked (it starts with a decreasing fashion then deviate from this logic), i reordered the items in a decreasing while being confident about the possibility of formulating other ordering strategies.

Notations:

  • The $\sum$ over an empty set is 0

  • ${n \choose k}$ is 0 for a negative value of k.

  • $d_i(b)$ (or $d_i$ for simplification) is the $i^{th}$ digit of b (it's also the coefficient of $2^{i-1}$ that can be easily formulated as a recursive function of b).

  • c(b) is the the number of digits set to 1 in b (easily formulable as a recursive function of b).

  • $S_m^i$ is the set of numbers given $c(b)=i$ and $b<2^m$

  • $r_l(b)$ is the (local) rank of b within its containing $S_m^i$ (The bigger a number is, smaller is its rank)

  • $r_g(b)$ is the (global) rank of the number b.

Properties:

  • $card(S_m^i)={m \choose i}$

  • If ($c(b)=1$) then $r_g(b)=r_l(b)$

  • $\forall$ b given $c(b)\geq2$ we can easily prove that: $ \begin{equation} \begin{split} r_g(b) =& \sum_{1\leq i\leq c(b)-1} card(S_m^i) + r_l(b)\\ \qquad =& \sum_{1\leq i\leq c(b)-1} {m \choose i} + r_l(b)\\ \end{split} \end{equation} $

  • $\forall \;b\; \in S_m^i$: $ \begin{equation} \begin{split} r_l(b) =& 1 \;+\; \sum_{1\leq j\leq m}{(1-d_{m-j})*{{m-j}\choose {i-(1+\sum_{1\leq k\leq j-1}{d_{m-k}})} }}*h_j^i(d)\\ \end{split} \end{equation} $ Where: $ \begin{equation} \begin{split} h_j^i(d) =&\frac{i-(\sum_{1\leq k\leq j-1}{d_{m-k}})}{max(1\;,\;(i-\sum_{1\leq k\leq j-1}{d_{m-k}}))}\; \end{split} \end{equation} $

The last formula can be intuitively explained as follows: Let d $\in S_m^i$ If the $j^th$ digit (coefficient of $2^{j-1}$) is set to 0, the rank of d is for sure after all the numbers having the $j^{th}$ digit set to 1 and having the same digits configuration as d before this $j^th$ digit. There are ${{m-j} \choose {i-(1+\sum_{1\leq k\leq j-1}{d_{m-k}})} }$ ones verifying this last assumption. Why ?

Let's take a closer look :

Assume d = $b_{m-1} b_{m-2} ... b_{j+1} \color{red}{b_j } b_{j-1} ... b_0 $

if $\color{red}{b_j } = 0$ then we know that the numbers having the same digit configuration as b before the $j^th$ bit (starting also with $b_{m-1} b_{m-2} ... b_{j+1}$ ) but having $b'_j=1$ are greater than b. How many are they?

First, we know that those numbers still have ${m-j}$ digits at the right of $b'_j$. How many of those remaining digits can be set to one?

Answer : ${i-(1+\sum_{1\leq k\leq j-1}{d_{m-k}})}$ because those numbers have already $\sum_{1\leq k\leq j-1}{d_{m-k}}$ digits set to 1, to which we add one as $p_j$ is also set to 1!

However, and here comes the aim of the function h, d should not be penalized by the 0 digits that comes at the right of its last 1 digit. For the simple reason that it is impossible to have other numbers that have digits set to one at this level (Remember that we're on sets of numbers with a fixed number of digits set to 1)

Therefore, we need to define a function that cancels the penalization for those zeros. As soon as j (the sum index) is at the level of those zeros the function takes 0, before that index the function takes 1.

An Example:

10000

01000

00100

00010

00001

11000

10100

10010

10001

01100

01010 -> The rank here is 11.

01001

...

$r_g(01010)={5 \choose 1} + r_l(01010)$

$r_l(01010)=1 + (1-0)*{4 \choose 1}*1 + (1-1)*{3 \choose 1}*1 + (1-0)*{2 \choose 0}*1 + (1-1)*{1 \choose 0}*1 + (1-0)*{0 \choose 0}*0$

$r_l(01010)= 1+ 4 + 0 + 1 + 0 + 0 = 6$

Then : $r_g(01010)= 5 + 6 = 11$