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

[filia&sofia]

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]

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]

... 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.

 

[Stefan Ram]

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]

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]

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

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

 

[Michael Press]

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.