0

I need to generate an m*n matrix with 1 and 0 where the sum of each row is 1 and each column is greater than or equal to 1. I'm trying this code but I don't know how to limit my condition on the columns, since sometimes I get zero columns and I need them all to have at least one 1. How could I limit the sum in the columns to be at least 1?

pt = [] sumr = 0 sumc = [] for i in range(n): quantity = random.choices([1]) row = np.zeros(p, dtype=int) idx = np.random.choice(range(p), quantity, replace=False) row[idx] = 1 pt.append(row) for j in range(len(pt[0])): sumc.append(sum([row[j] for row in pt]))     print(sumc)
Improve this question
1
  • Are there any requirements other than the two you've mentioned? Otherwise, you could just create an identity matrix of m*n and append random rows to it with a one somewhere to get the desired result. Moreover, you could then shuffle around the rows to get a more random matrix which still satisfies the requirements. Commented Mar 22, 2023 at 11:17

2 Answers 2

Reset to default
1

If I understood correctly what you're trying to do, you could define a simple optimization problem and solve it to find an m*n matrix that fits to your constraints.

To do so, first you will have to install an optimization package. I recommend using a package like PuLP. To install PuLP, run the following command:

pip install pulp

Here's an example on how you can create your matrix, by defining and solving an optimization problem with PuLP:

import pandas as pd import pulp M = 6 # Number of rows in the Matrix N = 5 # Number of columns in the Matrix # IMPORTANT: `M` needs to be greater than or equal to `N`, # otherwise it's impossible to generate a matrix, # given your problem set of constraints. # Create the problem instance prob = pulp.LpProblem("MxN_Matrix", sense=pulp.LpMaximize) # Generate the matrix with binary variables matrix = pd.DataFrame( [ [ pulp.LpVariable(f"i{row}{col}", cat=pulp.LpBinary, upBound=1, lowBound=0) for col in range(1, N + 1) ] for row in range(1, M + 1) ] ) # Set the constraints to the problem # Constraint 1: Each row must have exactly 1 element equal to 1 for row_sum in matrix.sum(axis=1): prob += row_sum == 1 # Constraint 2: Each column must have at least 1 element equal to 1 for col_sum in matrix.sum(axis=0): prob += col_sum >= 1 # Set an arbitrary objective function prob.setObjective(matrix.sum(axis=1).sum()) # Solve the problem status = prob.solve() # Print the status of the solution print(pulp.LpStatus[status]) # Retrieve the solution result = matrix.applymap(lambda value: value.varValue).astype(int) print(result) # Prints: # # 0 1 0 0 0 # 0 0 1 0 0 # 0 0 0 0 1 # 0 1 0 0 0 # 0 0 0 1 0 # 1 0 0 0 0

We can check that both your constraints are satisfied, by calculating the sum of each row, and column:

Sum of each row:

result.sum(axis=1) # Returns: # # 0 1 # 1 1 # 2 1 # 3 1 # 4 1 # 5 1 # dtype: int64

Sum of each column:

result.sum() # Returns: # # 0 1 # 1 2 # 2 1 # 3 1 # 4 1 # dtype: int64

NOTE

It's important to note that in order to create a matrix that satisfies the constraints of your problem, your matrix must have a number of rows greater than or equal to the number of columns. Since each column must have at least 1 element equal to 1 and each row needs to have exactly 1 element equal to 1, it's impossible for example to generate a matrix with 2 rows and 5 columns, since only 2 out of the 5 columns can contain an element that is not equal to zero.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

I would just create a matrix with ones in random places, and then check if there are still zero columns once we near the end so we don't leave any empty:

import numpy as np import random def make_mat(m, n): if (n > m): print("Invalid matrix dimensions.") return mat = np.zeros((m,n)) zero_cols = [True]*n # keep track of zero columns for row in range(m): # if there are N zero cols and N rows remaining, place 1 at randomly selected zero column place if len(np.where(zero_cols)[0]) == (m - row): idx = random.choice(np.where(zero_cols)[0]) # otherwise, just select a random index else: idx = random.randint(0, n-1) mat[row][idx] = 1 zero_cols[idx] = False return mat print(make_mat(10, 8))

However, this can be simplified if we make use of an identity matrix:

import numpy as np def make_mat_id(m, n): if (n > m): print("Invalid matrix dimensions.") return id_mat = np.identity(n) # add rows with one in random place mat = np.concatenate((id_mat, [np.where(np.arange(n) == np.random.choice(np.arange(n)), 1, 0) for _ in range(m-n)])) # make sure we no longer have the identity matrix np.random.shuffle(mat) return mat print(make_mat_id(10, 8)
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.