How do I find all 32 bit binary numbers that have exactly six 1 and rest 0

Question

I could do this in brute force, but I was hoping there was clever coding, or perhaps an existing function, or something I am not realising...

So some examples of numbers I want:

00000000001111110000
11111100000000000000
01010101010100000000
10101010101000000000
00100100100100100100

The full permutation. Except with results that have ONLY six 1's. Not more. Not less. 64 or 32 bits would be ideal. 16 bits if that provides an answer.

Answer 1

I think what you need here is using the itertools module.

BAD SOLUTION

But you need to be careful, for instance, using something like permutations would just work for very small inputs. ie:

Something like the below would give you a binary representation:

>>> ["".join(v) for v in set(itertools.permutations(["1"]*2+["0"]*3))]
['11000', '01001', '00101', '00011', '10010', '01100', '01010', '10001', '00110', '10100']

then just getting decimal representation of those number:

>>> [int("".join(v), 16) for v in set(itertools.permutations(["1"]*2+["0"]*3))]
[69632, 4097, 257, 17, 65552, 4352, 4112, 65537, 272, 65792]

if you wanted 32bits with 6 ones and 26 zeroes, you'd use:

>>> [int("".join(v), 16) for v in set(itertools.permutations(["1"]*6+["0"]*26))]

but this computation would take a supercomputer to deal with (32! = 263130836933693530167218012160000000 )

DECENT SOLUTION

So a more clever way to do it is using combinations, maybe something like this:

import itertools

num_bits = 32
num_ones = 6
lst = [
    f"{sum([2**vv for vv in v]):b}".zfill(num_bits)
    for v in list(itertools.combinations(range(num_bits), num_ones))
]
print(len(lst))

this would tell us there is 906192 numbers with 6 ones in the whole spectrum of 32bits numbers.

CREDITS:

Credits for this answer go to @Mark Dickinson who pointed out using permutations was unfeasible and suggested the usage of combinations

Answer 2

Well I am not a Python coder so I can not post a valid code for you. Instead I can do a C++ one...

If you look at your problem you set 6 bits and many zeros ... so I would approach this by 6 nested for loops computing all the possible 1s position and set the bits...

Something like:

 for (i0=   0;i0<32-5;i0++)
  for (i1=i0+1;i1<32-4;i1++)
   for (i2=i1+1;i2<32-3;i2++)
    for (i3=i2+1;i3<32-2;i3++)
     for (i4=i3+1;i4<32-1;i4++)
      for (i5=i4+1;i5<32-0;i5++)
       // here i0,...,i5 marks the set bits positions

So the O(2^32) become to less than `~O(26.25.24.23.22.21/16) and you can not go faster than that as that would mean you miss valid solutions...

I assume you want to print the number so for speed up you can compute the number as a binary number string from the start to avoid slow conversion between string and number...

The nested for loops can be encoded as increment operation of an array (similar to bignum arithmetics)

When I put all together I got this C++ code:

int generate()
    {
    const int n1=6;     // number of set bits
    const int n=32;     // number of bits
    char x[n+2]; // output number string
    int i[n1],j,cnt; // nested for loops iterator variables and found solutions count
    for (j=0;j<n;j++) x[j]='0'; x[j]='b'; j++; x[j]=0;  // x = 0
    for (j=0;j<n1;j++){ i[j]=j; x[i[j]]='1'; } // first solution
    for (cnt=0;;)
        {
//      Form1->mm_log->Lines->Add(x);   // here x is the valid answer to print
        cnt++;
        for (j=n1-1;j>=0;j--) // this emulates n1 nested for loops
            {
            x[i[j]]='0'; i[j]++;
            if (i[j]<n-n1+j+1){ x[i[j]]='1'; break; }
            }
        if (j<0) break;
        for (j++;j<n1;j++){ i[j]=i[j-1]+1; x[i[j]]='1'; }
        }
    return cnt;         // found valid answers
    };

When I use this with n1=6,n=32 I got this output (without printing the numbers):

cnt = 906192

and it was finished in 4.246 ms on AMD A8-5500 3.2GHz (win7 x64 32bit app no threads) which is fast enough for me...

Beware once you start outputing the numbers somewhere the speed will drop drastically. Especially if you output to console or what ever ... it might be better to buffer the output somehow like outputting 1024 string numbers at once etc... But as I mentioned before I am no Python coder so it might be already handled by the environment...

On top of all this once you will play with variable n1,n you can do the same for zeros instead of ones and use faster approach (if there is less zeros then ones use nested for loops to mark zeros instead of ones)

If the wanted solution numbers are wanted as a number (not a string) then its possible to rewrite this so the i[] or i0,..i5 holds the bitmask instead of bit positions ... instead of inc/dec you just shift left/right ... and no need for x array anymore as the number would be x = i0|...|i5 ...