algorithm - 在行和列中具有两个不相邻的非零值的等概率随机平方二进制矩阵的算法

Question

如果有人能给我一个算法，让我：
创建一个包含0和1项的随机方阵，以便
每行每列都包含两个非零项，
两个非零项不能相邻，
所有可能的矩阵都是等价的。
现在，我设法实现点1和点2，执行以下操作：使用行和列的适当排列，可以将这样的矩阵转换为具有以下形式的块的对角块矩阵

1 1 0 0 ... 0
0 1 1 0 ... 0
0 0 1 1 ... 0
.............
1 0 0 0 ... 1

所以我从这样一个矩阵开始，使用[0，…，n-1]的分区，并通过随机排列行和列来对其进行置乱。不幸的是，我找不到一种方法来整合邻接条件，而且我确信我的算法不会对所有的矩阵一视同仁。
更新
我已经达到了第三点。答案其实就在我眼皮底下：我正在创建的块矩阵包含了考虑邻接条件所需的所有信息。首先是一些属性和定义：
一个合适的矩阵定义了 [1, ..., n]的排列，可以像这样构建：在 1行中选择一个1。包含此项的列在与1不同的行 a中正好包含另一个等于1的项。同样，row a在列中包含另一个条目1，该列在row b中包含第二个条目1，依此类推。这将开始一个置换 1 -> a -> b ...。
例如，使用以下矩阵，从标记的条目开始

v
1 0 1 0 0 0 | 1
0 1 0 0 0 1 | 2
1 0 0 1 0 0 | 3
0 0 1 0 1 0 | 4
0 0 0 1 0 1 | 5
0 1 0 0 1 0 | 6
------------+--
1 2 3 4 5 6 |

我们得到排列 1 -> 3 -> 5 -> 2 -> 6 -> 4 -> 1。
这种置换的循环导致前面提到的块矩阵。我还提到使用行和列上的任意置换对块矩阵进行置乱，以重建与需求兼容的矩阵。
但是我使用了任何排列，这导致了一些相邻的非零项。为了避免这种情况，我必须选择将块矩阵中相邻的行（和列）分开的排列。实际上，更准确地说，如果两行属于同一个块并且是循环连续的（块的第一行和最后一行也被认为是连续的），那么我要应用的排列必须将这些行移动到最终矩阵的非连续行中（在这种情况下，我将调用不兼容的两行）。
所以问题变成：如何建立所有这样的排列？
最简单的想法是通过随机添加与前一个行兼容的行来逐步构建排列。作为一个例子，考虑使用partition n = 6和相应的块矩阵的情况

1 1 0 0 0 0 | 1
0 1 1 0 0 0 | 2
1 0 1 0 0 0 | 3
0 0 0 1 1 0 | 4
0 0 0 0 1 1 | 5
0 0 0 1 0 1 | 6
------------+--
1 2 3 4 5 6 |

这里的行 6 = 3 + 3、 1和 2是相互不兼容的，还有 3、 4和 5。选择一个随机行，比如 6。
我们将把排列写成数组： 3表示 [2, 5, 6, 4, 3, 1]， 1 -> 2， 2 -> 5， 3 -> 6，…这意味着块矩阵的行 2将成为最终矩阵的第一行，行 5将成为第二行，以此类推。
现在让我们通过随机选择一行来构建一个合适的排列，比如说 3：
p = [3, ...]
接下来，将在与 3： 4、 5和 6兼容的其余行中随机选择下一行。假设我们选择 4：
p = [3, 4, ...]
下一个选择必须在 1和 2之间进行，例如 1：
p = [3, 4, 1, ...]
等等： p = [3, 4, 1, 5, 2, 6]。
将此置换应用于块矩阵，我们得到：

1 0 1 0 0 0 | 3
0 0 0 1 1 0 | 4
1 1 0 0 0 0 | 1
0 0 0 0 1 1 | 5
0 1 1 0 0 0 | 2
0 0 0 1 0 1 | 6
------------+--
1 2 3 4 5 6 |

这样做，我们可以垂直隔离所有非零项。对于列也必须这样做，例如使用置换 p' = [6, 3, 5, 1, 4, 2]来最终获得

0 1 0 1 0 0 | 3
0 0 1 0 1 0 | 4
0 0 0 1 0 1 | 1
1 0 1 0 0 0 | 5
0 1 0 0 0 1 | 2
1 0 0 0 1 0 | 6
------------+--
6 3 5 1 4 2 | 

因此，这似乎非常有效，但是构建这些排列需要谨慎，因为很容易陷入困境：例如，使用 n=6和partition 6 = 2 + 2 + 2，遵循前面设置的构造规则可能会导致 p = [1, 3, 2, 4, ...]。不幸的是， 5和 6是不兼容的，所以选择其中一个会使最后的选择变得不可能。我想我已经找到了所有导致死胡同的情况。我将用 r表示剩下的一组选择：
p = [..., x, ?]， r = {y}与 x和 y不兼容
p = [..., x, ?, ?]， r = {y, z}与 y不兼容（无法选择）
z， x与 p = [..., ?, ?]和 r = {x, y}不兼容（任何选择都会导致情况1）
x， y与 p = [..., ?, ?, ?]， r = {x, y, z}和 x循环连续（选择 y或 z将导致情况2，选择 x将导致情况3）
z， y且 p = [..., w, ?, ?, ?]为3个循环（既不能选择 r = {x, y, z}也不能选择 xwy，选择 x将导致情况3）
y， z具有4个循环（任何选择都会导致情况4）
p = [..., ?, ?, ?, ?]， r = {w, x, y, z}的 wxyz是3个循环（选择 p = [..., ?, ?, ?, ?]将导致情况4，选择任何其他将导致情况4）
现在看来，下面的算法给出了所有合适的排列：
只要有严格的5个以上的数字选择，随机选择其中兼容的。
如果还有5个数字可供选择：如果剩余的数字包含3个周期或4个周期，则中断该周期（即，选择属于该周期的数字）。
如果还有4个数字可供选择：如果剩余的数字包含三个循环连续的数字，请选择其中一个。
如果还有3个数字可供选择：如果剩余的数字包含两个循环连续的数字，请选择其中一个。
我很确定这允许我产生所有合适的排列，因此，所有合适的矩阵。
不幸的是，根据所选的分区，每个矩阵都将被多次获得。

Answer 1

（更新了测试结果、示例运行和下面的代码片段。）
您可以使用动态编程来计算每个状态产生的解的数量（以比暴力算法更有效的方式），并使用这些（预计算）值来创建等概率随机解。
以7x7矩阵为例；开始时，状态为：

0,0,0,0,0,0,0  

这意味着有七个相邻的未使用列。在第一行加上两个后，状态可以是：

0,1,0,0,1,0,0  

两列中有一列。在第二行中添加一个后，状态可以是：

0,1,1,0,1,0,1  

在填充了三行之后，一个列的最大值可能为两个；这将有效地将矩阵分割成两个独立的区域：

1,1,1,0,2,0,1  ->  1,1,1,0 + 0,1  

这些区域是独立的，因为将它们添加到不同的区域时，无相邻区域规则没有影响，并且区域的顺序对解的数量没有影响。
为了使用这些状态作为解决方案类型的签名，我们必须将它们转换为规范符号。首先，我们必须考虑到这样一个事实，即只有一个列在下一行中可能不可用，因为它们在当前行中包含一个列。因此，我们必须使用三元符号，而不是二进制符号，例如：

2,1,1,0 + 0,1  

其中2表示该列在当前行中使用（而不是列中有2个）。下一步，我们应该把这两个换成一个。
此外，我们还可以将分离的组镜像，以将它们放入字典中最小的符号：

2,1,1,0 + 0,1  ->  0,1,1,2 + 0,1  

最后，我们将分离的组从小到大，然后词典编纂，这样在更大的矩阵中的状态可以是：

0,0 + 0,1 + 0,0,2 + 0,1,0 + 0,1,0,1  

然后，在计算每个状态产生的解的数量时，我们可以使用memoization，使用每个状态的规范符号作为键。
创建一个状态和每个状态的解的数目的字典只需要做一次，一个大矩阵的表也可以用于小矩阵。
实际上，您将生成一个介于0和解决方案总数之间的随机数，然后对于每一行，您将查看可以从当前状态创建的不同状态，查看每个状态将生成的唯一解决方案的数量，并查看哪个选项导致与您的随机生成数对应的解决方案。
请注意，每个状态和对应的键只能出现在特定的行中，因此您可以将键存储在每行的单独字典中。
试验结果
使用未优化的javascript进行的第一次测试给出了非常有希望的结果。使用动态规划，计算10x10矩阵的解的数量现在需要一秒钟，而暴力算法需要几个小时（这是算法中只需要做一次的部分）。包含签名和解的数量的字典的大小随着每一步大小接近2.5的递减因子而增长；生成它的时间以大约3的因子增长。
这些是解决方案的数量、状态、签名（字典的总大小）和每行的最大签名数（每行最大字典）：

size                           unique solutions          states    signatures    max/row

 4x4                                               2            9           6           2  
 5x5                                              16           73          26           8  
 6x6                                             722          514         107          40  
 7x7                                          33,988        2,870         411         152  
 8x8                                       2,215,764       13,485       1,411         596  
 9x9                                     179,431,924       56,375       4,510       1,983  
10x10                                 17,849,077,140      218,038      13,453       5,672  
11x11                              2,138,979,146,276      801,266      38,314      14,491  
12x12                            304,243,884,374,412    2,847,885     104,764      35,803  
13x13                         50,702,643,217,809,908    9,901,431     278,561      96,414  
14x14                      9,789,567,606,147,948,364   33,911,578     723,306     238,359  
15x15                  2,168,538,331,223,656,364,084  114,897,838   1,845,861     548,409  
16x16                546,386,962,452,256,865,969,596                4,952,501   1,444,487  
17x17            155,420,047,516,794,379,573,558,433               12,837,870   3,754,040  
18x18         48,614,566,676,379,251,956,711,945,475               31,452,747   8,992,972  
19x19     17,139,174,923,928,277,182,879,888,254,495               74,818,773  20,929,008  
20x20  6,688,262,914,418,168,812,086,412,204,858,650              175,678,000  50,094,203

（用C++获得的附加结果，使用一个简单的128位整数实现）。
例子
5x5矩阵的字典如下所示：

row 0:  00000  -> 16        row 3:  101    ->  0
                                    1112   ->  1
row 1:  20002  ->  2                1121   ->  1
        00202  ->  4                1+01   ->  0
        02002  ->  2                11+12  ->  2
        02020  ->  2                1+121  ->  1
                                    0+1+1  ->  0
row 2:  10212  ->  1                1+112  ->  1
        12012  ->  1
        12021  ->  2        row 4:  0      ->  0
        12102  ->  1                11     ->  0
        21012  ->  0                12     ->  0
        02121  ->  3                1+1    ->  1
        01212  ->  1                1+2    ->  0

解的总数是16；如果我们随机选取0到15之间的一个数，例如13，我们可以找到相应的（即14）解，如下所示：

state:      00000  
options:    10100  10010  10001  01010  01001  00101  
signature:  00202  02002  20002  02020  02002  00202  
solutions:    4      2      2      2      2      4  

这告诉我们，第14个解是选项00101的第2个解。下一步是：

state:      00101  
options:    10010  01010  
signature:  12102  02121  
solutions:    1      3  

这告诉我们，第二个解决方案是选项01010的第一个解决方案。下一步是：

state:      01111  
options:    10100  10001  00101  
signature:  11+12  1112   1+01  
solutions:    2      1      0  

这告诉我们，第1个解是选项10100的第1个解。下一步是：

state:      11211  
options:    01010  01001  
signature:  1+1    1+1  
solutions:    1      1  

这告诉我们，第一个解决方案是选项01010的第一个解决方案。最后一步是：

state:      12221  
options:    10001  

与随机选择的数字13对应的5x5矩阵是：

0 0 1 0 1  
0 1 0 1 0  
1 0 1 0 0
0 1 0 1 0  
1 0 0 0 1  

下面是一个快速的“n”脏代码示例；运行代码片段以生成签名和解决方案计数字典，并生成一个随机的10x10矩阵（生成字典需要一秒钟；完成后，它将在半毫秒内生成随机解决方案）：

function signature(state, prev) {
    var zones = [], zone = [];
    for (var i = 0; i < state.length; i++) {
        if (state[i] == 2) {
            if (zone.length) zones.push(mirror(zone));
            zone = [];
        }
        else if (prev[i]) zone.push(3);
        else zone.push(state[i]);
    }
    if (zone.length) zones.push(mirror(zone));
    zones.sort(function(a,b) {return a.length - b.length || a - b;});
    return zones.length ? zones.join("2") : "2";

    function mirror(zone) {
        var ltr = zone.join('');
        zone.reverse();
        var rtl = zone.join('');
        return (ltr < rtl) ? ltr : rtl;
    }
}

function memoize(n) {
    var memo = [], empty = [];
    for (var i = 0; i <= n; i++) memo[i] = [];
    for (var i = 0; i < n; i++) empty[i] = 0;
    memo[0][signature(empty, empty)] = next_row(empty, empty, 1);
    return memo;

    function next_row(state, prev, row) {
        if (row > n) return 1;
        var solutions = 0;
        for (var i = 0; i < n - 2; i++) {
            if (state[i] == 2 || prev[i] == 1) continue;
            for (var j = i + 2; j < n; j++) {
                if (state[j] == 2 || prev[j] == 1) continue;
                var s = state.slice(), p = empty.slice();
                ++s[i]; ++s[j]; ++p[i]; ++p[j];
                var sig = signature(s, p);
                var sol = memo[row][sig];
                if (sol == undefined) 
                    memo[row][sig] = sol = next_row(s, p, row + 1);
                solutions += sol;
            }
        }
        return solutions;
    }
}

function random_matrix(n, memo) {
    var matrix = [], empty = [], state = [], prev = [];
    for (var i = 0; i < n; i++) empty[i] = state[i] = prev[i] = 0;
    var total = memo[0][signature(empty, empty)];
    var pick = Math.floor(Math.random() * total);
    document.write("solution " + pick.toLocaleString('en-US') + 
        " from a total of " + total.toLocaleString('en-US') + "<br>");
    for (var row = 1; row <= n; row++) {
        var options = find_options(state, prev);
        for (var i in options) {
            var state_copy = state.slice();
            for (var j in state_copy) state_copy[j] += options[i][j];
            var sig = signature(state_copy, options[i]);
            var solutions = memo[row][sig];
            if (pick < solutions) {
                matrix.push(options[i].slice());
                prev = options[i].slice();
                state = state_copy.slice();
                break;
            }
            else pick -= solutions;
        }
    }
    return matrix;

    function find_options(state, prev) {
        var options = [];
        for (var i = 0; i < n - 2; i++) {
            if (state[i] == 2 || prev[i] == 1) continue;
            for (var j = i + 2; j < n; j++) {
                if (state[j] == 2 || prev[j] == 1) continue;
                var option = empty.slice();
                ++option[i]; ++option[j];
                options.push(option);
            }
        }
        return options;
    }
}

var size = 10;
var memo = memoize(size);
var matrix = random_matrix(size, memo);
for (var row in matrix) document.write(matrix[row] + "<br>");

下面的代码片段显示了10x10大小的矩阵的签名和解决方案计数字典。我使用的签名格式与上面的解释稍有不同：区域由“2”而不是加号分隔，在前一行中有加号的列用“3”而不是“2”标记。这显示了如何将密钥以2×n位整数（填充2）的形式存储在文件中。

function signature(state, prev) {
    var zones = [], zone = [];
    for (var i = 0; i < state.length; i++) {
        if (state[i] == 2) {
            if (zone.length) zones.push(mirror(zone));
            zone = [];
        }
        else if (prev[i]) zone.push(3);
        else zone.push(state[i]);
    }
    if (zone.length) zones.push(mirror(zone));
    zones.sort(function(a,b) {return a.length - b.length || a - b;});
    return zones.length ? zones.join("2") : "2";

    function mirror(zone) {
        var ltr = zone.join('');
        zone.reverse();
        var rtl = zone.join('');
        return (ltr < rtl) ? ltr : rtl;
    }
}

function memoize(n) {
    var memo = [], empty = [];
    for (var i = 0; i <= n; i++) memo[i] = [];
    for (var i = 0; i < n; i++) empty[i] = 0;
    memo[0][signature(empty, empty)] = next_row(empty, empty, 1);
    return memo;

    function next_row(state, prev, row) {
        if (row > n) return 1;
        var solutions = 0;
        for (var i = 0; i < n - 2; i++) {
            if (state[i] == 2 || prev[i] == 1) continue;
            for (var j = i + 2; j < n; j++) {
                if (state[j] == 2 || prev[j] == 1) continue;
                var s = state.slice(), p = empty.slice();
                ++s[i]; ++s[j]; ++p[i]; ++p[j];
                var sig = signature(s, p);
                var sol = memo[row][sig];
                if (sol == undefined) 
                    memo[row][sig] = sol = next_row(s, p, row + 1);
                solutions += sol;
            }
        }
        return solutions;
    }
}

var memo = memoize(10);
for (var i in memo) {
    document.write("row " + i + ":<br>");
    for (var j in memo[i]) {
        document.write("&quot;" + j + "&quot;: " + memo[i][j] + "<br>");
    }
}