1. 首页
  2. 问题
  3. 在行和列中具有两个不相邻的非零值的等概率随机平方二进制矩阵的算法
一尘不染

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

algorithm

如果有人可以将我引向允许我执行以下操作的算法，那就太好了：

  1. 创建一个具有条目0和1的随机方阵，这样
  2. 每行每列正好包含两个非零条目，
  3. 两个非零条目不能相邻，
  4. 所有可能的矩阵都是等价的。

现在，我设法做到以下几点：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]的分区的矩阵开始，并通过随机排列行和列来对其进行加扰。不幸的是，我找不到整合邻接条件的方法，而且我很确定我的算法不会平等对待所有矩阵。

更新资料

我已经设法达到了第3点。答案实际上是直截了当：我正在创建的块矩阵包含考虑邻接条件所需的所有信息。首先是一些属性和定义：

  • 一个合适的矩阵定义[1, ..., n]了可以构建的排列，如下所示：选择1 in row 1。包含该条目的列在a不同于1的行上包含正好等于1的a另一个条目。同样，行在列中包含另一个条目1，该行在行上包含第二个条目1 b，依此类推。这开始进行排列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。

  • 这种排列的 周期 导致了我前面提到的块矩阵。我还提到在行和列上使用任意排列对块矩阵进行 加扰 ，以重建符合要求的矩阵。

但是我使用了 任何
排列，这导致了一些相邻的非零条目。为避免这种情况，我必须选择将块矩阵中相邻行（和列）分开的排列。实际上，更确切地说，如果两行属于同一块并且 周期性地
连续（一个块的第一行和最后一行也被认为是连续的），那么我要应用的排列必须将这些行移为非连续最终矩阵的两行（在这种情况下，我将称两行 不兼容 ）。

因此，问题就变成了： 如何建立所有这些排列？

最简单的想法是通过随机添加与前一个兼容的行来逐步构建排列。例如，考虑n = 6使用分区6 = 3 + 3和相应块矩阵的情况

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 |

在此行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=6and partition 6 = 2 + 2 + 2，遵循先前设置的构造规则可能会导致p = [1, 3, 2, 4, ...]。不幸的是，5和6是不相容的，因此选择一个或其他品牌最后的选择是不可能的。我想我发现了所有导致死胡同的情况。我将通过r其余选择来表示：

  1. p = [..., x, ?]，r = {y}与x和y不兼容
  2. p = [..., x, ?, ?]，r = {y, z}与y和z被与两个不相容x（不可以作出选择）
  3. p = [..., ?, ?]，r = {x, y}与x和y不兼容（任何选择都会导致情况1）
  4. p = [..., ?, ?, ?]，r = {x, y, z}具有x，y并且z是周期性连续的（选择x或z会导致情况2，选择y情况3）
  5. p = [..., w, ?, ?, ?]，r = {x, y, z}与xwy作为一个3个周期（均未x也不y可以被选择，在选择z将导致情况3）
  6. p = [..., ?, ?, ?, ?]，r = {w, x, y, z}与wxyz作为一个4循环（任何选择将导致情况4）
  7. p = [..., ?, ?, ?, ?]，r = {w, x, y, z}与xyz作为一个3个周期（选择w将导致情况4中，在选择任何其他会导致情况4）

现在看来，以下算法给出了所有合适的排列：

  • 只要严格选择5个以上的数字，就可以在兼容的数字中随机选择。
  • 如果还有5个数字可供选择：如果其余数字包含3个循环或4个循环，则中断该循环（即，选择属于该循环的数字）。
  • 如果还有4个数字可供选择：如果其余数字包含三个循环连续的数字，请选择其中一个。
  • 如果还有3个数字可供选择：如果其余数字包含两个循环连续的数字，请选择其中一个。

我非常确定，这使我能够生成所有合适的排列，从而生成所有合适的矩阵。

不幸的是，根据选择的分区，每个矩阵都会获得几次。


阅读 236

收藏
2020-07-28

共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

这些区域是独立的，因为在将相邻区域规则添加到不同区域时，no-adjacent-ones规则不起作用，并且区域的顺序对解决方案数没有影响。

为了将这些状态用作解决方案类型的签名，我们必须将它们转换为规范的表示法。首先，我们必须考虑这样一个事实，即其中只有1个的列在下一行可能不可用，因为它们在当前行中包含一个。因此，我们必须使用三元表示法来代替二进制表示法，例如：

2,1,1,0 + 0,1

其中2表示此列已在当前行中使用（而不是该列中有2个）。下一步，我们应该将两者重新转换为1。

此外，我们还可以镜像单独的组，将它们放入按字典顺序最小的符号中：

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

然后，在计算每个状态产生的解的数量时，我们可以使用将每个状态的规范表示法作为键的记忆。

创建状态字典以及每个状态的解决方案数量仅需执行一次，并且较大矩阵的表也可以用于较小矩阵。

实际上，您将生成一个介于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

（使用简单的128位整数实现，使用C ++获得的其他结果。要计算状态，必须使用每个状态作为单独的签名来运行代码，而我无法使用最大的签名。）

例

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

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

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

这是一个简短的代码示例；运行该代码段以生成签名和解决方案计数字典，并生成一个随机的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>");

    }

}
2020-07-28