Generate all permutations of n entries in a w x h matrix

Question

I'd like to generate all the permutations of n entries in a w x h matrix: example with a 2x2 matrix and n = 1:

| 1 0 |
| 0 0 |

| 0 1 |
| 0 0 |

| 0 0 |
| 1 0 |

| 0 0 |
| 0 1 |

example with a 3x3 matrix and n = 2 (partial):

| 0 0 1|
| 0 0 1|
| 0 0 0|

| 1 0 0|
| 0 0 1|
| 0 0 0|

...

I would like to avoid the usage of numpy, so I think itertool is the way to go. I am looking at one dimensional solutions but all I got is something slightly different , like itertools.product that iterates with a fixed number of values, e.g.

itertools.product([0,'n'],repeat=6)

[(0, 0, 0, 0, 0, 0),....('n', 'n', 'n', 'n', 'n', 'n')]

any hint would be gladly appreciated

Answer 1

There are w * h available positions in which you want to place n 1's and fill the rest with 0's.

You can create all possible combinations of positions for the n 1's by using itertools.combinations:

>>> w = 2
>>> h = 2
>>> n = 2
>>> list(itertools.combinations(range(w * h), n))
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]

To create the actual matrix (as a list of 1's and 0's) from one of the positions tuples you can for example use a list comprehension:

>>> positions = (1, 3)
>>> [1 if i in positions else 0 for i in range(w * h)]
[0, 1, 0, 1]

For very large n the lookup i in positions becomes inefficient and it would be better to change this to a function like:

def create_matrix(positions):
    matrix = [0] * w * h
    for i in positions:
        matrix[i] = 1
    return matrix

Now you can put everything together:

>>> [[1 if i in p else 0 for i in range(w * h)]
...  for p in itertools.permutations(range(w * h), n)]
[[1, 1, 0, 0], [1, 0, 1, 0], [1, 0, 0, 1], [1, 1, 0, 0], [0, 1, 1, 0], [0, 1, 0, 1],
 [1, 0, 1, 0], [0, 1, 1, 0], [0, 0, 1, 1], [1, 0, 0, 1], [0, 1, 0, 1], [0, 0, 1, 1]]

Or, if you use the create_matrix function:

>>> [create_matrix(p) for p in itertools.permutations(range(w * h), n)]