Generate a list of binary numbers where n bits are set to 1-CodePudding

I want to generate a list of binary numbers with m digits, where n bits are set to 1 and all others are set to 0. For example, let's say m is 4. I want to generate a list of binary numbers with 4 bits. Of the 16 numbers, 6 of them have 2 bits set to 1, with the others being all 0s.

I want to generate a list for any m bits with n bits set to 1, at the very least for the case of where n = 2. But I'm not sure what process to follow. I could of course brute-force it and generate all numbers that are m bits then check each one individually, but for a larger number of bits that could take a while. I feel like there must be a neater mathematical trick to find out the answer.

I'd appreciate any pointers of where to start. I don't mind if answers are in pseudocode or any language, so long as they're clear.

The XY problem

I'm trying to solve a chess problem, where there are two pieces on the board. First I'm trying to generate all the valid combinations of two pieces on the board, which I'm planning to do by treating the chessboard as a 64-bit binary number (0000 0000 0000 0000 .. 0011) where an on-bit is a piece. To do this I need to find an elegant way to generate the list of binary numbers.

Edit: I've tried implementing the naive algorithm in Python just for demonstration. It's taking an awful long while to execute on my VS Code for m = 64, so definitely isn't the best solution:

n = 2
m = 64
combos = []
for i in range(2 ** m):
    bin_s = str(format(i, f'0{m}b'))
    if bin_s.count('1') == n:
        combos.append(bin_s)

for c in combos:
    print(c)

print(f"There are {len(combos)} combinations")

CodePudding user response：

This is called lexicographically next permutation, which is available in many bit hacking sites.

https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

Starting with x = 0b000000111 e.g. for 3 bits, one iterates until x & (1 << m) (or there's an overflow if m == word_size).

uint64_t next(uint64_t v) {
    uint64_t 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.
    return (t   1) | (((~t & -~t) - 1) >> (__builtin_ctz(v)   1));  
}

uint64_t v = 15; // 4 bits
do {
   my_func(v);
   if (v == 0xf000000000000000ull) {
       break;
   }
   v = next(v);
} while (true);

CodePudding user response：

Use https://docs.python.org/3/library/itertools.html#itertools.combinations to produce the set of indexes at which you have a 1. Turning that into a binary number is straightforward.

If you want this in another language, the documentation has native Python code to solve the problem.