0

Say I have a matrix (array) where elements are in the set {0,1} subject to the constraint that all rows and columns each sum to 1.

matches = np.array([[0,0,1],
                    [1,0,0],
                    [0,1,0]])

Is there a means to generate all possible such matrices that satisfy the above constraint?

Here's a naive attempt taking inspirational from a vaguely related question/answer,

import itertools

a = ['A','B','C']
b = ['X','Y','Z']

def get_permutations(a,b):
  index_map = {val:idx for idx,val in enumerate(a)}
  index_map.update({val:idx for idx,val in enumerate(b)})
  
  perms = [list(zip(x,b)) for x in itertools.permutations(a,len(b))]
  possible = []
  for p in perms: 
    temp_arr = np.zeros([len(a),len(b)])    
    for tup in p:
      x,y = index_map[tup[0]], index_map[tup[1]]
      temp_arr[x,y] = 1
    possible.append(temp_arr)
  return possible 


get_permutations(a,b) 

>>>
[array([[1., 0., 0.],
        [0., 1., 0.],
        [0., 0., 1.]]), array([[1., 0., 0.],
        [0., 0., 1.],
        [0., 1., 0.]]), array([[0., 1., 0.],
        [1., 0., 0.],
        [0., 0., 1.]]), array([[0., 0., 1.],
        [1., 0., 0.],
        [0., 1., 0.]]), array([[0., 1., 0.],
        [0., 0., 1.],
        [1., 0., 0.]]), array([[0., 0., 1.],
        [0., 1., 0.],
        [1., 0., 0.]])]

My question is: Is there a more condensed or otherwise faster way to return the list of arrays meeting the constraint mentioned above?

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
jbuddy_13
  • 902
  • 2
  • 12
  • 34

1 Answers1

1

Your solutions seem to be quite fast, there are not many things that can be corrected. Here is what I came up with

import itertools
import numpy as np

a = ['A','B','C']
b = ['X','Y','Z']

def get_permutations(a,b):
    n = len(a)
    possible = []
    for perm in itertools.permutations(range(n), n):
        matrix = np.zeros([n, n])
        i = 0
        for j in perm:
            matrix[i, j] = 1
            i += 1
        possible.append(matrix)
    return possible

get_permutations(a,b)

While your answer on average takes 3.17784857749939e-05 seconds, mine takes 9.6732497215271e-06 seconds (10000 test samples). The difference is really really small, but If you really need the fastest solution, consider this.

Really the slowest part is itertools.permuatations(), but I haven't found an alternative with considerable speed adventages.

K.Mat
  • 1,341
  • 11
  • 17