generating 2D bit array variants with specific algorythm

[Peter Otten]

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...