CODEWITHSUNDEEP
pythonlistmathcombinations
Confuto
Confuto

Reputation: 291

Python generate all possible combinations of matrix

I need to generate all combinations of a matrix in Python. The input will be two integers n and m, and I need to generate all possible states of that matrix with 1 and 0 as possible values.

For example:

n = 3 m = 2
[[0 0 0] [1 0 0] [1 1 0]
 [0 0 0] [0 0 0] [0 0 0]
 [0 0 0],[0 0 0],[0 0 0] . . . . .
]

Is there a clean and efficient way to do this given I will not know the values for n and m until runtime? The highest value used will be n = 16 m = 16.

Upvotes: 5

Views: 7454

Answers (3)

JustBeingHelpful
JustBeingHelpful

Reputation: 18980

You might be better off to refrain from using the word "combinations", since this implies a single finite set in set theory. Your example has three finite sets. Possibly use the word variants or enumerations to be more general.

The Cartesian Product requires three loops. Build matrix how you please; below is a two-index dictionary with a value being the bit/assertion result. Since you know you will always have three loops, pass in m_set, n_set and bit_set as arguments. For clarity, I defined them as explicit sets. Omit the underscores. If you wanted a limitless number of sets, you can use recursion.

def cartesian_product_three_finite_sets(mset, nset, bitset):

  count = 0
  m_set = {'1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','16'}
  n_set = {'1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','16'}
  bit_set = {'0','1'}
  struct_variants = {}

  for m in m_set:
    for n in n_set:
      for bit in bit_set:
         count += 1 
         struct_variants = set_two_index_dict(struct_variants, m, n, bit)
         # construct matrix

def set_two_index_dict(variable, index1, index2, value):
    try:
        if variable[index1][index2] != None:
            variable[index1][index2] = value
    except KeyError:
        variable.setdefault(index1, {})[index2] = value
    except TypeError:
        pass 
    return variable

Upvotes: 0

yatu
yatu

Reputation: 88226

One way is by generating all binary sequences of length m*n in a list comprehension, and reshaping them into a (m,n) shaped nested list on each iteration.

A simple way to generate all sequences is by taking the cartesian product of 01 with n*m repeats, which will be produce 2^(m*n) combinations:

from itertools import product
m=3
n=3

x = [[list(i[x:x+m]) for x in range(0, len(i), m)] for i in product("01", repeat=m*n)]

Output 

[[['0' '0' '0']
  ['0' '0' '0']
  ['0' '0' '0']]

 [['0' '0' '0']
  ['0' '0' '0']
  ['0' '0' '1']]

 [['0' '0' '0']
  ['0' '0' '0']
  ['0' '1' '0']]
 ...

print(len(x))
# 512

Upvotes: 5

Graipher
Graipher

Reputation: 7186

If you want all matrices at once, just produce flat lists using itertools.product and numpy.reshape them:

from itertools import product
import numpy as np

n, m = 2, 2

x = product([1, 0], repeat=n*m)
x = np.reshape(list(x), (-1, n, m))
print(x)

With the output for 2x2:

array([[[1, 1],
        [1, 1]],

       [[1, 1],
        [1, 0]],

       [[1, 1],
        [0, 1]],

       [[1, 1],
        [0, 0]],

       [[1, 0],
        [1, 1]],

       [[1, 0],
        [1, 0]],

       [[1, 0],
        [0, 1]],

       [[1, 0],
        [0, 0]],

       [[0, 1],
        [1, 1]],

       [[0, 1],
        [1, 0]],

       [[0, 1],
        [0, 1]],

       [[0, 1],
        [0, 0]],

       [[0, 0],
        [1, 1]],

       [[0, 0],
        [1, 0]],

       [[0, 0],
        [0, 1]],

       [[0, 0],
        [0, 0]]])

Note that for n, m = 16, 16 there are 2**(16*16) combinations, which is about 10**77, so much too large to fit into memory. In that case you probably have to process each matrix on its own:

def get_combinations(n, m):
    for flat in product([1, 0], repeat=n*m):
        yield np.reshape(flat, (n, m))

Which you can use like this:

from itertools import islice

for m in islice(get_combinations(3, 3), 3):  # only get the first three
    print(m)

[[1 1 1]
 [1 1 1]
 [1 1 1]]
[[1 1 1]
 [1 1 1]
 [1 1 0]]
[[1 1 1]
 [1 1 1]
 [1 0 1]]

Upvotes: 5

Related Questions