generate binary representation of numbers from 1 to 2^k-1

Question

I would like to obtain a list of binary represented integers in range 1... 2^k-1. Or otherwise, I need a list of all possible combinations of k bits. So, for example, given that k is 3 I need:

As I am planning on doing this in Java, I was thinking of using a BitSet for representing each number, and storing a value in a list, but I think this question could be language-agnostic. Basically, I need to figure out the algorithm for generating the entire set.

I think I need a recursive solution, something that would take into account the previously set bit.

void fill(int k, int i, boolean wasSet) {
    if (i==k) return;
        BitSet bs = new BitSet();
        for (int j=0; j<k; j++) {
          if (!wasSet) {
              bs.set(i);
              fill(k, i, true);
          } else {
              fill(k, j, false);
          }
    }

Note: this function prototype is obviously very wrong.

Note2: I would really really like to avoid using strings, as I later need to use this values to perform some other calculations, and BitSet comes quite handy for that

I was really surprised that I could only find a "duplicate" of this question in relation to Prolog... but that doesn't really help you in writing Java code. — Robin Green, Nov 17 '13 at 20:14

score 6 · Answer 1 · edited May 23 '17 at 12:07

6

You can have something as below:

for(int i=0 ; i<n ; i++){
  System.out.println(Integer.toBinaryString(i));
}

where n is the biggest number which you want to have.

update

To use BitSet java 7 has a BitSet.valueOf(byte[]) and BitSet.toByteArray().

For more details have a look to this post.

edited May 23 '17 at 12:07

Community

1
1

answered Nov 17 '13 at 20:15

tokhi

21,044
23
95
105

I would really really like to avoid using strings, as I later need to use this values to perform some other calculations, and BitSet is quite handy – Maggie Nov 17 '13 at 20:18

rolfl · Answer 2 · 2013-11-17T22:04:12.693

Odd question, some advanced concepts, but then some logic gaps as well.

Still, if you want bitsets for each value, do the same thing (as tokhi suggested) anyway:

int size = 1 << bits;
ArrayList<BitSet> results = new ArrayList<>(size);
for (int val = 1; val < size; val++) {
    BitSet bs = new BitSet(bits);
    results.add(bs);
    for (int b = 0; b < bits; b++) {
        if ( ((val >>> b) & 1) == 1) {
           bs.set(b);
        }
    }
}

EDIT

After some 'chat' about whether recursion or loops are better, I have put together this test...

I have modified my code above to be slightly more efficient, but, I have made relatively large changes to Dukeling's code so that it returns all BitSets instead of just modifying one and not storing the results.

Note that there is a 'bug' in the recursive code because it returns the no-bits-set value which is not supposed to be part of the results.....

Anyway, this is just food for thought.

Here's my test code:

import java.util.ArrayList;
import java.util.BitSet;

public class Junk {

    private static final ArrayList<BitSet> loop(final int bits) {
        int size = 1 << bits;
        ArrayList<BitSet> results = new ArrayList<>(size);
        for (int val = 1; val < size; val++) {
            BitSet bs = new BitSet(bits);
            results.add(bs);
            int v = val;
            int b = 0;
            while (v != 0) {
                if ( (v & 1) == 1) {
                   bs.set(b);
                }
                b++;
                v >>>= 1;
            }
        }
        return results;
    }

    private static final ArrayList<BitSet> recurse(final int bits) {
        ArrayList<BitSet> retval = new ArrayList<BitSet>();
        BitSet bitset = new BitSet(bits);
        fill(bitset, 0, bits, retval);
        return retval;
    }


    private static final void fill(final BitSet bs, final int k, final int n, final ArrayList<BitSet> results)
    {
       if (k == n) {
          results.add((BitSet)bs.clone());
          return;
       }
       bs.set(k, false);
       fill(bs, k+1, n, results);
       bs.set(k, true);
       fill(bs, k+1, n, results);
    }

    private static final void exercise(final int bits) {

        double acnt = 0;
        double bcnt = 0;
        long atime = 0L;
        long btime = 0L;

        for (int i = 0; i < 1000; i++) {
            final long as = System.nanoTime();
            acnt += recurse(bits).size();
            atime += System.nanoTime() - as;
            final long bs = System.nanoTime();
            bcnt += loop(bits).size();
            btime += System.nanoTime() - bs;
        }

        acnt /= 1000;
        bcnt /= 1000;

        System.out.printf("    Bits %d: ms/call -> recurse %.3fms loop %3fms (recurse %.1f/%d loop %f.1/%d\n",
                bits, atime / 1000000.0, btime / 1000000.0, acnt, 1<<bits, bcnt, (1 << bits) - 1);
    }

    public static void main(String[] args) {
        System.out.println("warmup");

        exercise(3);
        exercise(2);
        exercise(1);

        System.out.println("real runs");

        exercise(1);
        exercise(2);
        exercise(3);
        exercise(4);
        exercise(5);
        exercise(6);
        exercise(7);
        exercise(8);
        exercise(9);
        exercise(10);
        exercise(11);

    }

}

here's the output on my machine:

warmup
Bits 3: ms/call -> recurse 12.324ms loop 7.109403ms (recurse 8.0/8 loop 7.000000.1/7
Bits 2: ms/call -> recurse 2.949ms loop 2.392226ms (recurse 4.0/4 loop 3.000000.1/3
Bits 1: ms/call -> recurse 1.681ms loop 1.038053ms (recurse 2.0/2 loop 1.000000.1/1
real runs
Bits 1: ms/call -> recurse 1.743ms loop 0.865739ms (recurse 2.0/2 loop 1.000000.1/1
Bits 2: ms/call -> recurse 1.996ms loop 0.261967ms (recurse 4.0/4 loop 3.000000.1/3
Bits 3: ms/call -> recurse 3.150ms loop 0.544942ms (recurse 8.0/8 loop 7.000000.1/7
Bits 4: ms/call -> recurse 4.876ms loop 0.932031ms (recurse 16.0/16 loop 15.000000.1/15
Bits 5: ms/call -> recurse 6.128ms loop 1.775841ms (recurse 32.0/32 loop 31.000000.1/31
Bits 6: ms/call -> recurse 9.937ms loop 3.209335ms (recurse 64.0/64 loop 63.000000.1/63
Bits 7: ms/call -> recurse 21.005ms loop 7.221974ms (recurse 128.0/128 loop 127.000000.1/127
Bits 8: ms/call -> recurse 38.715ms loop 16.410275ms (recurse 256.0/256 loop 255.000000.1/255
Bits 9: ms/call -> recurse 69.904ms loop 41.330404ms (recurse 512.0/512 loop 511.000000.1/511
Bits 10: ms/call -> recurse 132.053ms loop 88.952120ms (recurse 1024.0/1024 loop 1023.000000.1/1023
Bits 11: ms/call -> recurse 255.921ms loop 193.370808ms (recurse 2048.0/2048 loop 2047.000000.1/2047

Converted my answer to a community wiki feel free to modify with improved results, whatever. — rolfl, Nov 17 '13 at 22:05
I meant to suggest improved recursive algorithm too.... Don't want to seem biased ... ;-) — rolfl, Nov 17 '13 at 22:11
Strangely enough, the recursive approach is faster for more than 6 bits on my machine (Java 7) (running your program as provided). And I believe, for a decent benchmark, you should record the results before and after the loop, not at each step of the loop. — Bernhard Barker, Nov 17 '13 at 22:14
Could have hit a GC cycle at 6-bits? As for the timing, yeah, but sometimes it's more interesting to the JIT compiler to interleave the code, gives both sides an equal 'opportunity' on there. — rolfl, Nov 17 '13 at 22:16
I see a couple of things I could improve... on the recurse side initializing the array-size would help, and the printf format for the loop side should be `%.3f` instead of `%3f` — rolfl, Nov 17 '13 at 22:20

score 3 · Accepted Answer · answered Nov 17 '13 at 20:29

3

Below is the recursive solution I came up with.

It simply, for every position, tries to set that bit, and then recurses.

It uses the same BitSet for all permutations. If you wish to have one for each, you'll probably have to copy it.

static BitSet bs = new BitSet(3);   
static void fill(int k, int n)
{
   if (k == n)
   {
      System.out.println(bs);
      return;
   }
   bs.set(k, false);
   fill(k+1, n);
   bs.set(k, true);
   fill(k+1, n);
}

public static void main(String[] args)
{
    fill(0, 3);
}

answered Nov 17 '13 at 20:29

Bernhard Barker

54,589
14
104
138

pretty nice. The space is explored as a tree, and the recursive call length is no more than n-k+1. – UmNyobe Nov 17 '13 at 20:36
I will accept this answer, because if somehow goes along with my thought process. Although the answer from @rolfl was great also – Maggie Nov 17 '13 at 20:40
@Maggie I am not fussed about who gets the answer 'points', but I should mention that recursion is not the most efficient solution for this problem.... your idea that you need recursion to solve this is the wrong 'pattern' for this problem. – rolfl Nov 17 '13 at 20:44
why? when generating the solution on paper, isn't the logic to follow similar? – Maggie Nov 17 '13 at 20:49
@rolfl I don't pick a recursive approach because I think it'll be faster, I pick it because the code is more intuitive (at least for me) and usually less error-prone. And the performance difference usually isn't *that* big - usually if you're doing anything non-trivial with the results, you're unlikely to notice the difference in performance. – Bernhard Barker Nov 17 '13 at 22:20
@Dukeling - recursion vs. loop is a fuzzy issue. I am not criticizing your answer as much as you think. My mind tends to settle on loops instead of recursion, but I still use recursion often. Interesting that compilers try to 'unroll' recursion when they can.... For what it's worth I thought you chose recursion because that's what the OP suggested it should use. – rolfl Nov 17 '13 at 22:38
@rolfl Well, it was somewhere between picking recursion and simply using it because that's what OP did. – Bernhard Barker Nov 17 '13 at 22:45

score 1 · Answer 4 · answered Nov 17 '13 at 20:21

Well, you can always increment manually:

int k = 3; //or something else

ArrayList<Boolean[]> combinations = new ArrayList<>();

boolean[] current;

void increment() {
    for(int i = 0; i<k; i++) {
        if(current[i]) {
            current[i] = false;
        } else {
            current[i] = true;
            break;
        }
    }
}

void fill() {
    current = new boolean[k];
    combinations.add(current);
    final int max = (int) Math.pow(2, k);
    for(int i = 1; i< max; i++) {
        current = current.clone(); //not sure about this -> google java array copy/clone
        increment();
        combinations.add(current);
    }
}

this will put LSB (least significant bit) at address 0, but since it contains all combinations, this shouldn't matter, it will only not be sorted if you represent it as if MSB (most -||-) would be at index 0.

score 0 · Answer 5 · answered Nov 18 '13 at 04:18

Here is a simple solution to problem it is equivalent to traversing a complete binary tree and recording each path.

public class Combinations {

    public static void combinations(int i,int k,char[]buff) {
        if(i<k) {

            buff[i] = '0';
            combinations(i+1,k,buff);
            buff[i] = '1';
            combinations(i+1,k,buff);
        }
        else System.out.println(String.valueOf(buff));
    }

    public static void main(String[] args) {
        int k = 3;
        combinations(0,k,new char[k]);
    }

}

score 0 · Answer 6 · edited Dec 13 '17 at 09:54

import java.util.LinkedList;
import java.util.Queue;

public class GenerateBNo 
{
    static void generatePrintBinary(int n)
    {
        Queue<String> q = new LinkedList<String>();
        q.add("1");
        while(n-- > 0)
        {
            String s1 = q.peek();
            q.remove();
            System.out.println(s1);
            String s2 = s1;
            q.add(s1 + "0");
            q.add(s2 + "1");
        }
    }
    public static void main(String[] args) 
    {
        int n=10;
        generatePrintBinary(n);
    }
}

generate binary representation of numbers from 1 to 2^k-1

6 Answers6

update

EDIT