Matrix pattern generation [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years ago.

Hello

I am working on java and I have to generate all the possible patterns(combinations) of M-by-N matrices such that in the same row there should not be more than a single 1, Same column may contain more than a single 1, Taking an example of 3*3 matrix, matrices generated should look like:

1 0 0  
1 0 0  
1 0 0  

0 1 0  
1 0 0  
1 0 0  

0 0 1  
1 0 0  
1 0 0  

1 0 0  
0 1 0  
1 0 0  

1 0 0  
0 0 1  
1 0 0  

1 0 0  
1 0 0  
0 1 0  

1 0 0  
1 0 0  
0 0 1  

0 1 0  
0 开发者_如何学运维1 0  
0 1 0  

1 0 0  
0 1 0  
0 1 0  

0 0 1  
0 1 0  
0 1 0  

0 1 0  
1 0 0  
0 1 0  

0 1 0  
0 0 1  
0 1 0  

..... and so on.

As I have already said that progrom should be flexible that can generate all such possible patterns for any value of M and N.

Please help me..

Thanks!

---

Here's one solution. ideone.com demo.

I bet it can be done with half the number of rows though.

public static Set<int[][]> chooseFrom(List<int[]> choices, int choose) {
    Set<int[][]> results = new HashSet<int[][]>();
    if (choose == 1) {
        for (int[] choice : choices)
            results.add(new int[][] { choice });
    } else {
        for (int[] choice : choices) {
            for (int[][] submatrix : chooseFrom(choices, choose - 1)) {
                int[][] matrix = new int[choose][];
                matrix[0] = choice;
                for (int r = 1; r < choose; r++)
                    matrix[r] = submatrix[r-1];
                results.add(matrix);
            }
        }
    }

    return results;
}

public static Set<int[][]> matrices(int M, int N) {
    List<int[]> possibleRows = new ArrayList<int[]>();

    for (int i = 0; i < N; i++) {
        int[] row = new int[N];
        row[i] = 1;
        possibleRows.add(row);
    }

    return chooseFrom(possibleRows, M);
}

Output for the 2x3 case:

[ 0 0 1 ]
[ 0 1 0 ]

[ 1 0 0 ]
[ 0 0 1 ]

[ 0 0 1 ]
[ 0 0 1 ]

[ 0 0 1 ]
[ 1 0 0 ]

[ 0 1 0 ]
[ 1 0 0 ]

[ 0 1 0 ]
[ 0 1 0 ]

[ 1 0 0 ]
[ 1 0 0 ]

[ 0 1 0 ]
[ 0 0 1 ]

[ 1 0 0 ]
[ 0 1 0 ]

---

I'd do it as three 1 dimensional arrays where there are logic checks to see if a given array is acceptable. By acceptable, I mean contains no more than a single 1. I'd then save this configuration since columns don't matter.

Once that's done with, I'd then iterate through all the possible valid array combinations and print them out using for loops for each array in question. I'd advice making a class to encapsulate each set of arrays and write some methods to traverse and print them correctly. I'd then put all of those objects in a linked list as they get generated and then traverse that list to print all of the possible options after generation.

---

As you can see there are per line exactly n possibilites for a 1 per row. So to enumerate all possible matrices you just loop over the col index and place a 1 in that col. As you want all rows and all combinations you have to do that now recursive for all rows, and volia: you have your solution.

(Your question does not even hint what you have already tried, nor where you get stuck, so the answer is very unspecific).

---

Hm... If i correct this is similar with permutation algorithm. look if you have 3x3 so it's same with find a permutation of 123 so permutation will like

111
112
113
121
131
...etc

and than convert/display it like array

111 
will be
100
100
100

112
will be
100
100
010

... etc

hope this will help

---

import java.util.Arrays;

public class MatrixPatternGenerator {

    public static void main(String[] args) {
        int M = Integer.parseInt(args[0]);
        int N = Integer.parseInt(args[1]);
                    int[] rows = new int[M];
        Arrays.fill(rows, 0);
                    System.out.println("Matrix number-> 1");
        printMatrix(M, N, rows);
        int cursor = M-1;
        while (true){
            if (rows[cursor]==N-1){
                if (cursor==0)
                    break;
                rows[cursor]=0;
                cursor--;
                continue;
            }
            rows[cursor]++;
                            printMatrix(M, N, rows);
            if (cursor<M-1){
                cursor = M-1;
            }
        }
    }
    public static void printMatrix(int M, int N, int[] rows){
                for (int i=0 ; i<M ; i++ ){
            for (int j=0 ; j<rows[i] ; j++){
                System.out.print(" 0");
            }
            System.out.print(" 1");
            for (int j=rows[i]+1 ; j<N ; j++){
                System.out.print(" 0");
            }
            System.out.println();
        }
        System.out.println();
            }

}