How to generate 2**40 possible binary numbers with conditions

Question

I want to generate all possible 2**N binary numbers with conditions that every array must have 20 of ones (1) like this:00000000001111111111111111111110000000000, I found methods of generating the binary matrix like this one:

import itertools
l = itertools.product([0, 1], repeat=N)

And I tried to generate it using Numpy but I get memory errors.

So is there any other methods?

2**40 is a large number ... Anyway, what do you mean by 20 ones? — Dani Mesejo, Nov 27 '19 at 17:45
`2**40` is `~10**12`. 1GB is `~10**9` bytes. How much memory do you have? — David Buck, Nov 27 '19 at 17:47
every array in the matrix generated must have 20 x 1 like this vector as an example: `00000000001111111111111111111110000000000` — Adelov, Nov 27 '19 at 17:47
Your memory problem is not with `numpy`. It's with your demends. — Aryerez, Nov 27 '19 at 17:48
Even the subset of the `2**40` numbers that has exactly 20 `1s` in their binary representation contains 137 trillion integers. Since each `int` requires at least 56 bytes, it's not surprising you ran out of memory. — chepner, Nov 27 '19 at 17:48
If the 1s have to be *consecutive*, then iterating over the full set of candidates is overkill. There's only 20 of them. — chepner, Nov 27 '19 at 17:49
Possible duplicate of [Iterate binary numbers with the same quantity of ones (or zeros) in random order](https://stackoverflow.com/questions/44568618/iterate-binary-numbers-with-the-same-quantity-of-ones-or-zeros-in-random-order) — David Buck, Nov 27 '19 at 17:52
Yes, buy about 10 TB of RAM, plus a computer that can use that much. — chepner, Nov 27 '19 at 17:52
Or do you just want a filter around the output of `itertools.product`? That's doable, though you won't be able to fully iterate over it in any reasonable amount of time, so you effectively will never reach the end of the set. — chepner, Nov 27 '19 at 17:55
I don't know; you still haven't explained what you actually want. No, you cannot store all the values in memory at once. No, you cannot even iterate over all the values in any reasonable amount of time. Why do you want/need these values in the first place? — chepner, Nov 27 '19 at 18:03
@chepner this what i am trying to do: https://stackoverflow.com/questions/59057203/trying-to-optimize-my-complex-function-to-excute-in-a-polynomial-time/59058159?noredirect=1#comment104365039_59058159 — Adelov, Nov 27 '19 at 21:49

score 1 · Answer 1 · answered Nov 27 '19 at 18:42

The intended problem size is not feasible, but here is an itetools-based generator of all n-bit numbers with k ones:

import itertools

def k_ones(n,k):
    """generates n-bit integers with exactly k ones"""
    for c in itertools.combinations(range(n),k):
        n = 0
        for i in c:
            n |= (1 << i)
        yield n

#test:

for i in k_ones(5,2):
    print(format(i,'05b'))

Output:

How to generate 2**40 possible binary numbers with conditions

1 Answers1