Velocity Reviews > Given an integer, what is the position of it as a combination?

# Given an integer, what is the position of it as a combination?

filia&sofia
Guest
Posts: n/a

 04-14-2011
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.

Paul N
Guest
Posts: n/a

 04-14-2011
On Apr 14, 9:37*pm, "filia&sofia" <(E-Mail Removed)> 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.

Peter Nilsson
Guest
Posts: n/a

 04-14-2011
"filia&sofia" <(E-Mail Removed)> wrote:
> ... So, in a way, this problem is about finding the "position"
> of a combination.

As such, it's a question on algorithms, not C. You're better off
posting to say comp.programming.

--
Peter

Stefan Ram
Guest
Posts: n/a

 04-14-2011
"filia&sofia" <(E-Mail Removed)> writes:
>Any ideas, links, etc? Thanks.

This seems to be a purely mathematical question.
I don't see how it is related to C specifically.

filia&sofia
Guest
Posts: n/a

 04-18-2011
On 14 huhti, 23:51, Paul N <(E-Mail Removed)> wrote:
> On Apr 14, 9:37*pm, "filia&sofia" <(E-Mail Removed)> 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).

filia&sofia
Guest
Posts: n/a

 04-18-2011
On 15 huhti, 01:21, Peter Nilsson <(E-Mail Removed)> wrote:
> "filia&sofia" <(E-Mail Removed)> wrote:
> > ... So, in a way, this problem is about finding the "position"
> > of a combination.

>
> As such, it's a question on algorithms, not C. You're better off
> posting to say comp.programming.
>
> --
> Peter

True. I was (still am) also interested in possible hacks in C to
achieve this.

Michael Press
Guest
Posts: n/a

 04-20-2011
In article
<(E-Mail Removed)>,
"filia&sofia" <(E-Mail Removed)> 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.

Here is a start.

Number bit positions starting at 0.
Suppose we have a bit pattern p.
b(p) = number of bits set in p.
h(p) = the bit pattern with exactly one bit set
at the highest bit position set in p.

We want to find
ord(p) = the index of p in the sequence of bit patterns
with exactly b(p) bits set.

Then
ord(p) = bincoeff(ord(h(p)), b(p)) + ord(p xor h(p)).

Consider 101010.

543210
ord(101010) = bincoeff(5, 3) + ord(1010)
= 10 + ord(1010)
= 10 + 3 + ord(10)
= 10 + 2 + 1 + 0
= 14

0 (000111)
1 (001011)
2 (001101)
3 (001110)
4 (010011)
5 (010101)
6 (010110)
7 (011001)
8 (011010)
9 (011100)
10 (100011)
11 (100101)
12 (100110)
13 (101001)
14 (101010)

Though why anybody wants this except as a school assignment
I do not know.

--
Michael Press