What is the fastest algorithm to computer all permutations of a binary number with same hamming weight?

Question

I want an algorithm to compute all permutations of a fixed size binary number with a given hamming weight. For example, if the hamming weight is 2 and the binary size is 4 then there are these outputs:

0011
0110
0101
1100
1010
1001

The number of such combinations is computed as C(n,r) in this example C(4,2) which is 6.

Note that you can solve this just by increasing a number from 0 to 2^n and see if the count is OK. However, it is not a fast solution. I am considering solving the problem using bitset class in C++, and I need to increase N.

I want to add that there is an obvious recursive algorithm for this problem. Due to stack overflow, it is not a good answer. I have received a good answer here from Gosper's hack. While, I need to scale up the input and maybe use an MPI implementation for it later, I need a scalable library. Unsigned int is not big enough and I would rather a scalable and fast library like bitset. The solution is not applicable here while there is no addition in bitset library. any other solution?

Ferren

While "lexicographically next bit-permutation" is great and efficient if you need one more item in the sequence and all you know was the previous result, you can do the dynamic programming search without recursion by tracking some state (in contrast, the "next-permutation" operation has to recover the state from the array each time). In particular "current bit location" (as index or mask), "count of unplaced zeros", and "count of unplaced ones", plus the working arbitrary-precision number, are sufficient. – Butternut

Answer 1

You can implement the "lexicographically next bit-permutation" using Gosper's Hack:

unsigned int v; // current permutation of bits 
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1
// Next set to 1 the most significant bit to change, 
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

Or if you don't have ctz (_BitScanForward on MSVC),

unsigned int t = (v | (v - 1)) + 1;  
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

Saucy

Answer 2

You can generate them in the following manner:

1. Initially, make a vector with n - r zeros in the beginning and r ones in the end(0011 for n = 4 and r = 2).

2. Then, repeat the following procedure:

   1. Find the rightmost one such that a zero is located to the left from it. If there is no such one, we are done.
   2. Move it to the left(by one position, that is, swap it with a zero).
   3. Move all the ones that are located to the right from it to the very end of the vector.
      For example, if we have 0110, we first move the rightmost one that can be moved to the left and get 1010, then we shift all ones to the right from it to the end of the vector and get 1001.

This solution has O(C(n, r) * n) time complexity. One more feature of this solution: it generates elements in lexicographical order.

Fleischer