在最后2个不相同的每一行写0和1

Question

我现在构建的逻辑中存在错误.应该发生的是我的代码应该显示0和1的网格.像这样:

001001
101101
010110
110010
001101

所以这里必须发生的是:

• 对于每一行,连续不能有多于2个相同类型的数字
• 这些数字是随机挑选的
• 对于每列,连续不能有超过2个相同类型的数字
• 按列或行的每种类型的数字最多可以有3个

编辑:进一步澄清确定所以我有这样一行:0 1 0 1 1 0 - 你可以看到总会有3 x 1和3 x 0 - 数字的顺序是随机挑选的(所以它可能会去0 1,或1 1,或0 0开始等) - 连续不能超过2个相同类型的数字,例如如果它是001100,你可以看到有2 0,那么它必须显示一个1,但是那时有2个1,所以它必须显示0.所以011100不会发生(连续3个1)或000101(连续3个0)

• 基于这一点,但现在不是必需的,同样没有2号连续必须适用于列(所以在我的成功例子不言而喻001001跨越,最多有2 0的连续,但往下看你会得到010101(也就是说,再次,连续不超过2)

所以我的代码如下:

    import java.util.Random;

public class Main {

    public static void main(String[] args) {
        int l = 6;
        int w = 6;
        Random rd = new Random();

        // Create a grid that is 6 x 6
        int[][] grid = new int[l][w];
        // for each row
        for (int i = 0; i < l; i++) {
            int zCount = 0;
            int oCount = 0;
            int current;
            int lastA = 2;
            int lastB = 2;
            // for each item in the row
            for (int j = 0; j < w; j++) {
                // set the current item to either 0 or 1
                current = rd.nextInt(2);
                // make sure there aren't already (e.g. 3 items out of 6)
                // items in the row
                if (j % 2 == 1) {
                    // hold every second element
                    lastA = current;
                } else {
                    // hold every first element
                    lastB = current;
                }
                if (current == 1) {
                    if (oCount != 3) {
                        if (lastA != lastB) {
                            // if the two previous items aren't the same
                            grid[i][j] = current;
                            // add to the counter
                            oCount++;
                        }
                    }
                }
                if (current == 0) {
                    if (zCount != 3) {
                        if (lastA != lastB) {
                            // if the two previous items aren't the same
                            grid[i][j] = current;
                            // add to the counter
                            zCount++;
                        }
                    }
                }
                System.out.print(grid[i][j]);
            }
            System.out.println(" ");
        }
    }
}

问题是它产生如下:

010010 
100001 
100010 
000010 
100001 
001000 

所以显然它不符合第一,第三或第四点.我完全不知道为什么!除了我没有初始化的列(第三点).

任何人都可以解决我的代码中的逻辑故障吗？

谢谢你的帮助!

Answer 1

这是我的程序解决方案,它试图尽可能减少所需代码的数量.它能够计算具有任意行和列的2D阵列,例如[6,6]或[4,7]或[3,8].算法的复杂性是O(n),其中n =行*列.

该程序计算一个任意的二维数组(网格),填充一个0或1.网格保证了以下特性,数学上制定:

∀r , c∈整数| 0≤r<grid.rows,0≤c<grid.columns:

r - 2≥0⇒基数(不同(网格[r] [c],网格[r-1] [c],网格[r-2] [c]))= 2

r + 2 <grid.rows⇒基数(不同(网格[r] [c],网格[r + 1] [c],网格[r + 2] [c]))= 2

c - 2≥0⇒基数(不同(网格[r] [c],网格[r] [c-1],网格[r] [c-2]))= 2

c + 2 <grid.columns⇒基数(distinct(grid [r] [c],grid [r] [c + 1],grid [r] [c + 2]))= 2

或换句话说:

网格既不包含行也不包含具有三个或更多连续0's或的列1's.

在Java代码下面,我将解释算法如何工作以及为什么设计原样:

public static void main(String[] args) {
    int[][] grid = anyGrid(8, 13);
}

private static int[][] anyGrid(int rows, int cols) {
    int[][] grid = new int[rows][cols];
    int row = 0;
    for (int col = 0; col - row < cols; col++) {
        for (int r = row; r >= 0 && col - r < cols;) {
            setBit(grid, r, col - r--);
        }
        if (row < rows - 1) row++;
    }
    return grid;
}

private static void setBit(int[][] grid, int row, int col) {
    int vInd = calcVerticalIndicator(grid, row, col);
    int hInd = calcHorizontalIndicator(grid, row, col);
    if (isPartiallyRestricted(vInd, hInd)) {
        grid[row][col] = flip(vInd);
    } else if (isFullyRestricted(vInd, hInd)) {
        grid[row][col] = vInd;
        grid[row - 1][col] = flip(vInd);
    } else {
        grid[row][col] = Math.abs(vInd) <= 1
                ? flip(vInd)
                : Math.abs(hInd) <= 1 ? flip(hInd) : anyBit();
    }
}

private static boolean isPartiallyRestricted(int vInd, int hInd) {
    return vInd == hInd;
}

private static boolean isFullyRestricted(int vInd, int hInd) {
    return vInd + hInd == 1;
}

private static int calcVerticalIndicator(int[][] grid, int row, int col) {
    return calcIndicator(grid, row - 1, col, row - 2, col, 2);
}

private static int calcHorizontalIndicator(int[][] grid, int row, int col) {
    return calcIndicator(grid, row, col - 1, row, col - 2, 4);
}

private static int calcIndicator(int[][] grid, int row1, int col1, int row2, int col2, int unrestricted) {
    try {
        return grid[row1][col1] * grid[row2][col2] + (grid[row1][col1] - grid[row2][col2]) * unrestricted;
    } catch (IndexOutOfBoundsException e) {
        return unrestricted;
    }
}

private static int anyBit() {
    return (int) (Math.random() * 2);
}

private static int flip(int bit) {
    return bit == 0 ? 1 : 0;
}

我们面临的挑战不是确保没有连续三​​个0's或1's仅连续或仅在一列中.挑战在于通过提供有效的算法来确保没有三个连续0's或1's既不在一行也不在一列中.

我们可能遇到的棘手情况如下:

让我们考虑这样一种情况,即蓝色轮廓的单元格顶部和左侧的所有单元格都已填充,并且不违反上面定义的规则.

• 图片a)我们想要填充具有蓝色轮廓的单元格.它顶部的两个单元格中有两个,0's而左边的单元格则填充了两个单元格1's.我们应该选择哪个值？由于对称性,如果我们选择a 0或a 无关紧要1.因此,让我们一起来吧0.

• 图片b)用0违反上面定义的一个规则填充蓝色轮廓的单元格:网格不包含具有三个或更多连续0's或的列1's.因此,我们必须改变蓝色单元格上方的两个单元格之一的值.

• 图象c)说我们改变,并立即开始蓝色单元上方,从该单元的值0到1.这可能导致违反某些规则,这些规则是由已修改单元格左侧的已填充单元格引起的.

• 图片d)但是违规将意味着左边的两个单元格必须具有值1.

• 图片e)这意味着它们顶部的两个单元必须具有0与我们假设的情况相矛盾的值.因此,立即更改蓝色轮廓的单元格顶部的单元格不会导致违反规则.

为了解决前提条件,已经填充了修改的单元格右侧没有单元格,该算法以对角线方式填充网格.细胞群按以下顺序出现:

我想解释的最后一件事是算法如何决定哪些值可供每个单元格选择.对于每个单元,它检查两个最顶部和两个最左边的单元并计算指示值.此值用于通过使用算术计算确定单元格的可能值,如下所示:

• 如果检查的两个单元都填充了0's返回指示器值0.

• 如果检查的两个单元都填充了1's返回指示器值1.

我选择了这两个值,因为它们以直观的方式传达了这个值是不允许的.

然后我选择了一个函数来进行通信,如果列单元格和行单元格都限制单元格填充相同的值.如果两个指标值相等,则情况就是这样.记住这个特性,因为当列单元格或行单元格没有限制时,我们必须找到该情况的值.

如果两个指标都限制值以使用不同的值填充单元格,则它们的总和为1.这是在没有限制条件时搜索适当指标值时必须记住的第二个特征.

算法必须做的最后一件事是在没有限制的情况下找到适当的值,而不会影响上面定义的唯一指标.

• 通过选择不同于0和1并且彼此不同的行和列指示符的值,可以实现当单元被相同值限制时保留指示.

• 当单元受两个值限制时保留指示可以通过选择大于1的值并且彼此具有至少为2的Δ来实现.

该算法确实表明值2和-2没有限制行,而值4和-4没有限制列.此值与用于标识其他两种情况的操作不冲突.

我希望这篇文档有助于理解整个程序以及它如何解决问题陈述.我很高兴听到你的意见.

Answer 2

给出的许多解决方案都非常长且复杂。这是一个代码非常少的解决方案（此处为 Ideone 示例）：

int row, col, n = 8;
int[][] grid = new int[n][n], cCount = new int[n][2], rCount = new int[n][2];
Deque<Entry<Integer,Integer>> freeInd = new ArrayDeque<Entry<Integer,Integer>>();
Random rand=new Random();
for(int i = 0; i < grid.length; i++){
    for(int j = 0; j < grid[0].length; j++){
        // Calcualte constraints: row, col = {-1, 0, 1},  -1 => no constraint.
        row = j > 1 && grid[i][j-2] == grid[i][j-1] ? (grid[i][j-1] == 0 ? 1:0):  
             (rCount[i][0] >= n/2 ? 1:                           // too many 0's
             (rCount[i][1] >= n/2 ? 0:-1));                      // too many 1's
        col = i > 1 && grid[i-2][j] == grid[i-1][j] ? (grid[i-1][j] == 0 ? 1:0):
             (cCount[j][0] >= n/2 ? 1:                           // too many 0's
             (cCount[j][1] >= n/2 ? 0:-1));                      // too many 1's
        grid[i][j] = row == -1 && col == -1 ? rand.nextInt(2):(row > -1 ? row:col);

        // Handle Constraints
        if( row == -1 && col == -1){                              // no constraint
            freeInd.push(new SimpleEntry<Integer,Integer>(i, j)); // add to free indices
        } else if( (row > -1 && col > -1 && row != col)           // constraint conflict
                || (row > -1 && rCount[i][row] >= n/2)            // count conflict
                || (col > -1 && cCount[j][col] >= n/2)){          // count conflict
            Entry<Integer, Integer> last = freeInd.pop();         // grab last free index
            while(i > last.getKey() || j > last.getValue()){
                j = (j-1+ n)%n;                                   // step indices back
                i = (j == n-1) ? i-1:i;   
                rCount[i][grid[i][j]]--;                          // reduce counters
                cCount[j][grid[i][j]]--;
            }
            grid[i][j] = grid[i][j] == 0 ? 1:0;                   // flip value
        }       
        rCount[i][grid[i][j]]++;                                  // increment counters
        cCount[j][grid[i][j]]++;
    }
}

这里的想法是，沿着矩阵的每一行添加 0 和 1，并遵守以下规则：

1. 如果当前索引不受约束（即可以是 0 或 1），我们随机选择一个值。
2. 如果当前索引受到约束，我们会强制它具有受约束的值。
3. 如果存在多个不一致的约束，我们将freeInd首先沿着矩阵的行逐步向后移动，减少给定值（0 或 1）的计数，从而恢复到最后一个无约束索引 ( )。例如，这是针对带有 的行完成的rCount[i][grid[i][j]]--。当最终到达不受约束的顶点时，翻转它的值。
4. 最后，增加当前行和列的值（0 或 1）计数。例如，这是针对具有以下内容的行完成的：rCount[i][grid[i][j]]++