So the mission is that I have to construct* a 2D integer matrix with randomly generated dimensions and values given the sums of its rows and columns. To elaborate, the 2d matrix only has ones and zeros- there are no other integers in it. Additionally, I must reconstruct it given only two 1d arrays- one array has the sums of the rows (basically each member of this 1d array indicates how many ones there were on that row) and a second 1d array that details the sums of the columns (same as other one). The solution must be implemented recursively.
The following code functions for matrices 4x4 and below (although performance notably degrades when inputting matrices 4x4 or larger- it sometimes works for 4x5 and 5x5 but performance is not guaranteed). The program specifications mandate that I be able to reconstruct any matrix up to 6x6 in dimensions. Could somebody help me make my code more efficient and explain how it works? Thanks,
*Exact reconstruction is not necessary, as there may be multiple solutions, but the outputted matrix must have the correct row and column sums as the original. ^Also, the language is Java.
- Code: Select all
// Name:
// Date:
public class MatrixRecreate_7_Yum
{
public static void main(String[] args)
{
int[][] matrix = create();
int[] rowcount = new int[matrix.length];
int[] colcount = new int[matrix[0].length];
count(matrix, rowcount, colcount);
display(matrix, rowcount, colcount);
re_create(rowcount, colcount);
}
public static int[][] create()
{
int[][] fin = new int[(int)(Math.random()*5)+2][(int)(Math.random()*4)+2];
//int[][] fin = new int[5][5];
for (int x = 0; x < fin.length; x++) {
for (int y = 0; y < fin[0].length; y++) {
fin[x][y] = (int)(Math.random()+.5);
}
}
return fin;
}
public static void count(int[][] matrix, int[] rowcount, int[] colcount)
{
for(int x = 0; x < matrix.length; x++) {
int temp = 0;
for(int y = 0; y < matrix[0].length; y++) {
temp = temp + matrix[x][y];
}rowcount[x] = temp;
}
for(int z = 0; z < matrix[0].length; z++) {
int temp = 0;
for(int a = 0; a < matrix.length; a++) {
temp = temp + matrix[a][z];
}colcount[z] = temp;
}
}
public static void display(int[][] matrix, int[] rowcount, int[] colcount)
{
System.out.print("---");
for(int x = 0; x < colcount.length; x++) {
System.out.print(colcount[x] + " ");
}System.out.println("\n");
for (int y = 0; y < rowcount.length; y++) {
System.out.print(rowcount[y] + ": ");
for(int z = 0; z < matrix[0].length; z++) {
System.out.print(matrix[y][z] + " ");
}System.out.println();
}
System.out.println();
}
public static void re_create(int[] rowcount, int[] colcount)
{
int[][] neo = new int[rowcount.length][colcount.length];
for (int x = 0; x < neo.length; x++) {
for (int y = 0; y < neo[0].length; y++) {
neo[x][y] = 0;
}
if(rowcount[x] <= neo[0].length/2) {
for(int y = 0; y < rowcount[x]; y++) {
neo[x][y] = 1;
}
}else {
for(int y = neo[0].length-rowcount[x]; y < neo[0].length; y++) {
neo[x][y] = 1;
}
}
}
recur(neo, rowcount, colcount, 0, 0);
}
private static void recur(int[][] m, int[] rowcount, int[] colcount, int row, int col) //recursive helper method
{
if(compare(m, rowcount, colcount)) //base case: if new matrix works
{
display(m, rowcount, colcount); //we're done!
System.out.println("Success!");
System.exit(0);
}else {
if(((rowcount[row]==0)||(rowcount[row]==m[0].length))&&(row-1>=0)) {recur(m, rowcount, colcount, row-1, col);}
try {
if(m[row][col] == m[row][col+1]){recur(m, rowcount, colcount, row, col+1);}
else{
int temp = m[row][col]; m[row][col] = m[row][col+1]; m[row][col+1]=temp;
recur(m, rowcount, colcount, row, col+1);
}
}catch (ArrayIndexOutOfBoundsException e) {
if (row == 0) {
recur(m, rowcount, colcount, m.length-1, 0);
}else {
if((double)rowcount[row] != (double)m.length/2.0) {
for(int x = 0; x < m[0].length; x++) {m[row][x] = 0;}
for(int y = 0; y < rowcount[row]; y++) {m[row][y] = 1;}
}
recur(m, rowcount, colcount, row-1, 0);//test with 0 = col-1
}
}catch (StackOverflowError e) {recur(m, rowcount, colcount, row, col);}
}
}
private static boolean compare(int[][] m, int[] rowcount, int[] colcount)
{
boolean fin = true;
int[] row1 = new int[rowcount.length]; int[] col1 = new int[colcount.length];
count(m, row1, col1);
for(int x = 0; x < rowcount.length; x++) {
fin = fin && (rowcount[x] == row1[x]);
}for (int y = 0; y < colcount.length; y++) {
fin = fin && (colcount[y] == col1[y]);
}return fin;
}
}
