0

好的，所以我的问题基本上是，例如，我有一个矩阵

010
101
111

只是随机的 1 和 0。所以我有数组rowcountand colcount，它计算每行和每列中的个数。所以rowcount对于 this is{1,2,3}和colcountis {2,2,2}。现在在另一种方法中，我得到了数组rowcountand colcount，在该方法中，我应该创建一个计数在rowcountandcolcount中的矩阵，但最终矩阵可以不同。比原来的。我想我应该用尽所有排列，直到矩阵起作用。基本情况必须保持不变。

注意：不能使用 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]++;

        }

     }

  }
4

2 回答 2

1

好吧，我决定实现一个解决方案，但是我将使用 Groovy（无论如何它是基于 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
于 2013-10-29T23:55:43.877 回答
0

好的，您的问题和评论表明您走在正确的轨道上。代码本身有点乱，显然已经经历了一些迭代。这不是很好，但没关系。

我相信你是对的，你必须“用尽”递归，直到找到与现有列/行数匹配的新结果。所以，从逻辑上解决问题。首先，创建一个可以将矩阵与行/列计数进行比较的方法。你称之为“比较（...）”。我假设您已经使用了这种方法;-)。这是标记递归结束的方法。当比较返回 true 时，您应该返回递归“堆栈”。你不应该做一个System.exit(...).

所以，递归的基本规则，你需要一个输入，一个输出，一个包含退出条件检查的方法体，如果条件不满足则递归调用......

您的问题有一个使事情复杂化的特定问题-如果每次降低递归级别时输入矩阵都需要进行复制。或者，您需要“撤消”您在升级时所做的任何更改。“撤消”方法更快（更少的内存副本）。

所以，过程如下，从一个全零矩阵开始。为全零起点调用递归函数。

int[][] matrix = new int[width][height];
int rpos = 0;
boolean found = recur(matrix, rowcount, colcount, 0, 0);

这就是它的调用方式，found如果我们找到了解决方案，它将是正确的。

与您的代码不同的是，recur现在返回一个boolean.

因此，我们的recur方法需要做： 1. 检查当前矩阵 - 如果匹配则返回 true。2. 进行有意义的更改（在我们添加的限制内） 3. 递归检查更改（并添加其他更改）。

您的方法没有输出，因此无法逃避递归。因此，添加一个（在这种情况下为布尔值）。

这可以工作的方式是我们从左上角开始，并尝试设置该位，并取消设置。对于每个条件（设置或未设置），我们递归地测试下一位是否在设置或未设置时匹配，依此类推......：

private static boolean recur(int[][] m, int[] rowcount, int[] colcount, 
        int row, int col) {
    if (compare(m, rowcount, colcount)) {
        // our matrix matches the condition
        return true;
    }
    if (row >= m.length) {
        return false;
    }

    int nextcol = col + 1;
    int nextrow = row;
    if (nextcol >= m[row].length) {
        nextcol = 0;
        nextrow++;
        if (nextrow > m.length) {
            return false;
        }
    }
    // OK, so nextrow and nextcol are the following position, and are valid.
    // let's set our current position, and tell the next level of recursion to
    // start playing from the next spot along
    m[row][col] = 1;
    if (recur(m, rowcount, colcount, nextrow, nextcol)) {
        return true;
    }
    // now unset it again
    m[row][col] = 0;
    if (recur(m, rowcount, colcount, nextrow, nextcol)) {
        return true;
    }
    return false;

}

上面的代码只是手写的，可能有bug等，不过还是试试吧。这里的教训是你需要测试你的条件，你需要一个策略......

于 2013-10-29T23:56:25.657 回答