好吧,我的问题基本上是,例如我有一个矩阵
010
101
111
只是随机的 1 和 0。因此,我有 rowcount
和 colcount
数组,它们计算每行和每列中的个数。因此,rowcount
为 {1,2,3}
,colcount
为 {2,2,2}
。现在,在另一种方法中,我得到了数组 rowcount
和 colcount
,在该方法中,我应该使用 rowcount
中的计数创建一个矩阵code> 和 colcount
,但最终矩阵可以不同。比原来的。我想我应该用尽所有排列,直到矩阵起作用。基本情况必须保持不变。
注意:不能使用 Math.random。
private static void recur(int[][] m, int[] rowcount, int[] colcount, int r, int c)
//recursive helper method
{
if(compare(m, rowcount, colcount)) //base case: if new matrix works
{
System.out.println();
System.out.println("RECREATED");
display(m, rowcount, colcount); //we're done!
System.exit(0);
}
else
{
int[] temp_r = new int[m.length];
int[] temp_c = new int[m[0].length];
count(m, temp_r, temp_c);
if(rowcount[r] > temp_r[r] && colcount[c] > temp_c[c])
m[r][c] = 1;
if(r+1 < m.length)
recur(m,rowcount,colcount,r+1,c);
if(rowcount[r] < temp_r[r] || colcount[c] < temp_c[c])
m[r][c] = 0;
if(c+1 < m[0].length)
recur(m,rowcount,colcount,r,c+1);
}
}
private static boolean compare(int[][] m, int[] rowcount, int[] colcount)
{
int[] temp_r = new int[m.length];
int[] temp_c = new int[m[0].length];
count(m, temp_r, temp_c);
for (int x = 0; x < temp_r.length; x++)
{
if(temp_r[x] != rowcount[x])
return false;
}
for (int y = 0; y < temp_c.length; y++)
{
if(temp_c[y] != colcount[y])
return false;
}
return true;
}
public static void count(int[][] matrix, int[] rowcount, int[] colcount)
{
for(int x=0;x<matrix.length;x++)
for(int y=0;y<matrix[0].length;y++)
{
if(matrix[x][y]==1)
{
rowcount[x]++;
colcount[y]++;
}
}
}
最佳答案
好吧,我决定实现一个解决方案,但我将使用 Groovy(无论如何它都是基于 Java 的),而不是 Java(您实际上没有指定解决方案需要使用的 Java)!我尝试尽可能使用 Java 语法,从中推断出 Java 代码并不困难(但它更加冗长!)
注意:
*生成随机位矩阵,不使用 Math.random()
*我将矩阵存储在字符串中,即 [[0,1],[1,0]] = "0110"
*我的解决方案很大程度上依赖于将整数转换为二进制字符串(这本质上就是您的矩阵!)
// Generate random matrix
int colSize = 3;
int rowSize = 4;
String matrix = '';
for (int i = 0; i < rowSize; i++){
String bits = Integer.toBinaryString(System.currentTimeMillis().toInteger());
matrix += bits.substring(bits.length() - colSize);
Thread.sleep((System.currentTimeMillis() % 1000) + 1);
}
def (cols1,rows1) = getCounts(matrix, colSize)
println "matrix=$matrix rows1=$rows1 cols1=$cols1"
// Find match (brute force!)
int matrixSize = colSize * rowSize
int start = 0
int end = Math.pow(Math.pow(2, colSize), rowSize) // 2 is number of variations, i.e. 0 and 1
for (int i = start; i <= end; i++){
String tmp = leftPad(Integer.toBinaryString(i), matrixSize, '0')
def (cols2,rows2) = getCounts(tmp, colSize)
if (cols1 == cols2 && rows1 == rows2){
println "Found match! matrix=$tmp"
break;
}
}
println "Finished."
String leftPad(String input, int totalWidth, String padchar){ String.format('%1$' + totalWidth + "s", input).replace(' ',padchar) }
int[][] getCounts(String matrix, int colSize){
int rowSize = matrix.length() / colSize
int[] cols = (1..colSize).collect{0}, rows = (1..rowSize).collect{0}
matrix.eachWithIndex {ch, index ->
def intval = Integer.parseInt(ch)
cols[index % colSize] += intval
rows[(int)index / colSize] += intval
}
[cols,rows]
}
给出输出:
matrix=001100011000 rows1=[1, 1, 2, 0] cols1=[1, 1, 2]
Found match! matrix=001001110000
Finished.
暴力搜索逻辑:
Given a rowcount of [1,2,3]
And a colcount of [2,2,2]
Iterate over all matrix combinations (i.e. numbers 0 - 511 i.e. "000000000" -> "111111111")
Until the new matrix combination's rowcount and colcount matches the supplied rowcount and colcount
关于java - 如何递归地用0和1填充矩阵?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19670759/