in_tyrannos
4/18/2011 8:49:00 PM
On 14 huhti, 23:51, Paul N <gw7...@aol.com> wrote:
> On Apr 14, 9:37 pm, "filia&sofia" <in_tyran...@hotmail.com> wrote:
>
>
>
>
>
> > Let's take a 32-bit "unsigned int" integer i, i: [0, 2^32).
>
> > Let's order a sequence of integers 0,1,2,...,2^32-1 as follows:
>
> > 1) first into groups of k-bits, k: [0,32]
> > 2) elements in each group into increasing order
> > 3) putting all 2^32 integers to a single sequence starting from group
> > where k=0 and then k=1,2,3,...,32
>
> > For example: 2-bit integers. i: [0,3]
> > 1) groups
> > - k=2. 1 ints. 11
> > - k=1. 2 ints. 10 and 01
> > - k=0. 1 ints. 00
> > 2) {00}, {01, 10}, {11}
> > 3) 00,01,10,11
>
> > It's easy to see that, for example, i=0b10 is the 3rd integer in this
> > case. But what if we have 32-bit integer. What is the "position" of it
> > when we have a integer sequence that follows the description? So, in a
> > way, this problem is about finding the "position" of a combination.
>
> > Any ideas, links, etc? Thanks.
>
> Can it be done using the formula for the number of combinations? IE
> the number of ways of choosing k from n is n! / k!(n-k)!
>
> For instance, consider the number 1011101. This has 5 ones, so it goes
> after all the 0 ones, 1 one, .. 4 ones; and it goes before all the 6
> ones, 7 ones etc. Which narrows down its position somewhat.
>
> And then, within the 5 ones group, it goes before all those that have
> a one in the first 15 bits. And it goes after all those that have no
> one in the first 16 bits.
>
> I think you can narrow down to the exact position just by counting up
> how many numbers come before and after the selected number.- Piilota siteerattu teksti -
>
> - Näytä siteerattu teksti -
Hi Paul! And thanks, with your help I found a solution: combinadic
(e.g. wikipedia for reference).