首页 文章

如何递归填充0和1的矩阵?

提问于
浏览
0

好的,基本上我的问题是,我有一个矩阵

010
101
111

只是随机的1和0 . 所以我有 rowcountcolcount 的数组,它们计算每行和每列中的数量 . 所以 rowcount 这是 {1,2,3}colcount{2,2,2} . 现在在另一种方法中,我得到了数组 rowcountcolcount ,并且在该方法中,我应该创建一个具有 rowcountcolcount 中的计数的矩阵,但是结束矩阵可以是不同的 . 比原来的 . 我想我应该用尽所有的排列,直到矩阵工作 . 基本情况必须保持不变 .

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

        }

     }

  }

2 回答

  • 0

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

    我相信你是对的,你必须'exhaust'递归,直到你找到一个与现有列/行计数相匹配的新结果 . 所以,从逻辑上解决问题 . 首先,创建一个可以将矩阵与行/列计数进行比较的方法 . 你称之为'compare(...)' . 我假设你已经有了这种方法;-) . 这是标记递归结束的方法 . 当compare返回true时,您应该返回递归'stack' . 你不应该做 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等,但尝试一下 . 这里的教训是你需要测试你的志气,你需要一个策略....

  • 1

    好吧,我决定实现一个解决方案,但是不是Java(你实际上没有指定解决方案需要进入),我将使用Groovy(无论如何都是基于Java的)!我试图在可能的情况下使用Java语法,从这里推断Java代码并不难(但它更冗长!)

    Note:

    *生成随机位矩阵,不使用Math.random()

    *我将我的矩阵存储在一个字符串中,即[[0,1],[1,0]] =“0110”

    *我的解决方案非常依赖于将整数转换为/从BinaryStrings转换(这基本上就是你的矩阵!)

    // 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
    

相关问题