generating 2D bit array variants with specific algorythm

Peter Otten __peter__ at web.de
Fri Nov 7 17:29:30 CET 2014

```Robert Voigtländer wrote:

> Hi,
>
> I need to generate all variants of a 2D array with variable dimension
> sizes which fit a specific rule. (up to 200*1000)
>
> The rules are:
> - Values are only 0 or 1
> - the sum of each line bust be 1
> - only valid results must be generated (generating all and only returning
> the valid results takes to long; that's what I tried already)
>
> So for a 2x2 array these would be the valid results:
>
> 10
> 01
>
> 01
> 10
>
> 10
> 10
>
> 01
> 01
>
>
> Must be possible with nested loops and a counter per line. But I don't get
> it.
>
> Can someone help?

Have a look at itertools.product(). If you need to code it in Python -- the
documentation has an example implementation.

from itertools import product

def f(n):
rows = [[0] * n for i in range(n)]
for i, row in enumerate(rows):
row[i] = 1
rows = [tuple(row) for row in rows]
return list(product(rows, repeat=n))

if __name__ == "__main__":
from pprint import pprint
pprint(f(2))
print("---")
pprint(f(3))

However, n**n is growing quite fast; you'll soon reach the limits of what is
feasible in Python. Maybe numpy has something to offer to push these limits
a bit. An optimisation would be to store the position of the 1, i. e.

01

10

00

11

for n=2. If you reorder these you get 0, 1, 2, 3. I think I'm seeing a
pattern...

```