array puzzle:generating all possible combinations

Question

hello, im doing a project and this part is rly important to me.i'll try to be as clear as possible.

suppose we have an mxn matrix with all 0s, i need to generate all possible combinations of the array in which only one element in a row is initialised to 1 and all the other elements in that row are 0s. similarly, in all the rows, exactly one element should be 1. ex: take a 3x2 matrix, the following should be the output:

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

the values within the square brackets is a 3x2 matrix,each row separated by a comma. so basically, an mxn matrix will have n power m number of combinations. anyone who can think of any possible way of solving this pls post it, its really important. thanks in advance

Answer 1

Since this sounds like homework I'm not going to give you a complete solution, but rather some steps in the right direction. Let's start with a 3x2 matrix. We can solve this using nested for loops:

int row0, row1, row2;
for(row0=0; row0<2; ++row0) {
  matrix[0][row0] = 1;
  for(row1=0; row1<2; ++row1) {
    matrix[1][row1] = 1;
    for(row2=0; row2<2; ++row2) {
      matrix[2][row2] = 1;
      print_matrix(matrix);
      matrix[2][row2] = 0;
    }
    matrix[1][row1] = 0;
  }
  matrix[0][row0] = 0;
}

Of course this isn't a very generic solution. It's easy to change this to a 3xm matrix (just replace the row#<2 with row#<m-1) but clearly this doesn't work for an nxm matrix. Everytime we increase n by one we need to add another for loop.

I leave it up to you to determine how to get rid of the nested for loops and use some other technique to generalize it.