wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> integer encoding with increasing number of bits
        
(Message started by: towr on Sep 16^th, 2018, 11:16pm)

Title: integer encoding with increasing number of bits
Post by towr on Sep 16^th, 2018, 11:16pm

I'm pondering whether there's a "simple" integer encoding where the number of bits set to 1 increase. So given an maximum integer size, you first count with all integers with only 0s, then with 1 bti set to 1, then with 2 bits set to 1 etc. But ideally there would be a simple way to encode and decode it.

The simplest way to count (with maxint=15) is probably like
0000
0001
0010
0100
1000
0011
0101
0110
1001
1010
1100
0111
1011
1101
1110
1111

But is there a simple way to map from value to representation and back? Or is there a better way?

Title: Re: integer encoding with increasing number of bit
Post by Grimbal on Sep 17^th, 2018, 2:46am

So far I have a method that works for the first 3 and the last 3 values. :-)

For the rest I have to think a bit more. I think I have a way that is faster than just generating the sequence.

Title: Re: integer encoding with increasing number of bit
Post by SMQ on Sep 17^th, 2018, 6:18am

A few properties of note:

- The second half of the sequence is the first half of the sequence inverted and reversed (which is true of many useful binary sequences.)

- The number of n-bit integers with k 1's is just the binomial coefficient (n/k)

- There is no closed form equation for partial sums of binomial coefficients. That makes it unlikely that there's a simple way to encode/decode the sequence.

--SMQ

Title: Re: integer encoding with increasing number of bit
Post by dudiobugtron on Sep 26^th, 2018, 7:10pm

I figured that ordering binary numbers by the number of bits set to 1 was equivalent to ordering elements of a powerset by size, so did a bit of research and I found a blog page (http://www.thelowlyprogrammer.com/2010/04/indexing-and-enumerating-subsets-of.html) that talks about enumerating subsets in size order (the article mentioned in the linked post calls it "Banker's order"), along with links to algorithms, papers and discussions about it.

I don't know how useful this would be to you, so apologies in advance if you end up reading it and getting no useful information!
Also, I did not generate any of the content myself, so it's certainly not a viable answer if this post was intended as a riddle (rather than general information gathering).

on 09/17/18 at 02:46:10, Grimbal wrote:

So far I have a method that works for the first 3 and the last 3 values. :-)

Title: Re: integer encoding with increasing number of bit
Post by Grimbal on Oct 6^th, 2018, 8:09am

Here are the conversion procedures to/from ABC encoding (Ascending Bit Count)
choose(n,k) is the binomial coefficient.


public static int convertToABC(int len, int value){
    int code = 0;
    int k = 0, c;
    while( (c = choose(len,k)) <= value && k < len){
        value -= c;
        k++;
    }
    for( int n = len-1 ; n >= 0 ; n-- ){
        code = code*2;
        if( value >= (c = choose(n,k)) ){
            value -= c;
            k--;
            code++;
        }
    }
    return code;
}

public static int convertFromABC(int len, int code){
    int value = 0;
    int k = 0;
    for( int n=0 ; n < len ; ++n ){
        if( (code&1) == 1 ){
            value += choose(n, ++k);
        }
        code /= 2;
    }
    while( k-->0 ){
        value += choose(len, k);
    }
    return value;
}