在行和列中具有两个不相邻的非零的等概率随机平方二进制矩阵的算法 [英] Algorithm for equiprobable random square binary matrices with two non-adjacent non-zeros in each row and column
问题描述
如果有人可以将我引向允许我执行以下操作的算法，那就太好了
It would be great if someone could point me towards an algorithm that would allow me to :
- 创建一个随机的方阵，其条目为0和1，这样
- 每一行和每一列正好包含两个非零条目，
- 两个非零条目不能相邻，
- 所有可能的矩阵都是等价的.
现在，我设法做到以下几点:1和2:可以使用行和列的适当排列将这样的矩阵转换为对角线块矩阵，其块的形式为
Right now I manage to achieve points 1 and 2 doing the following : such a matrix can be transformed, using suitable permutations of rows and columns, into a diagonal block matrix with blocks of the form
1 1 0 0 ... 0
0 1 1 0 ... 0
0 0 1 1 ... 0
.............
1 0 0 0 ... 1
因此，我从使用[0，...，n-1]的分区的矩阵开始，并通过随机排列行和列来对其进行加扰.不幸的是，我找不到整合邻接条件的方法，而且我很确定我的算法不会平等地对待所有矩阵.
So I start from such a matrix using a partition of [0, ..., n-1] and scramble it by permuting rows and columns randomly. Unfortunately, I can't find a way to integrate the adjacency condition, and I am quite sure that my algorithm won't treat all the matrices equally.
更新
我设法达到了第3点.答案实际上是直截了当:我正在创建的块矩阵包含考虑邻接条件所需的所有信息.首先是一些属性和定义:
I have managed to achieve point 3. The answer was actually straight under my nose : the block matrix I am creating contains all the information needed to take into account the adjacency condition. First some properties and definitions:
- 一个合适的矩阵定义
[1, ..., n]的排列，可以这样构建:在1行中选择1.包含该条目的列在与<1>不同的行a上正好包含另一个等于1的条目.同样，行a在列中包含另一个条目1，该列在行b上包含第二个条目1，并且很快.这将开始排列1 -> a -> b ....
- a suitable matrix defines permutations of
[1, ..., n]that can be build like so: select a 1 in row1. The column containing this entry contains exactly one other entry equal to 1 on a rowadifferent from 1. Again, rowacontains another entry 1 in a column which contains a second entry 1 on a rowb, and so on. This starts a permutation1 -> a -> b ....
例如，具有以下矩阵，从标记的条目开始
For instance, with the following matrix, starting with the marked entry
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.
-
这种排列的
- 循环导致了我前面提到的块矩阵.我还提到了加扰块矩阵，它在行和列上使用任意排列来重建符合要求的矩阵.
- the cycles of such a permutation lead to the block matrix I mentioned earlier. I also mentioned scrambling the block matrix using arbitrary permutations on the rows and columns to rebuild a matrix compatible with the requirements.
但是我使用的是 any 排列，这导致了一些相邻的非零条目.为避免这种情况，我必须选择将块矩阵中相邻行(和列)分开的排列.实际上，更准确地说，如果两行属于同一块并且循环是连续的(一个块的第一行和最后一行也被认为是连续的)，那么我要应用的排列必须将这些行移到最终矩阵的非连续行中(在这种情况下，我将称为不兼容的两行).
But I was using any permutation, which led to some adjacent non-zero entries. To avoid that, I have to choose permutations that separate rows (and columns) that are adjacent in the block matrix. Actually, to be more precise, if two rows belong to a same block and are cyclically consecutive (the first and last rows of a block are considered consecutive too), then the permutation I want to apply has to move these rows into non-consecutive rows of the final matrix (I will call two rows incompatible in that case).
问题就变成了:如何建立所有这样的排列?
最简单的想法是通过随机添加与上一个兼容的行来逐步构建排列.例如，考虑使用分区6 = 3 + 3和相应的块矩阵
The simplest idea is to build a permutation progressively by randomly adding rows that are compatible with the previous one. As an example, consider the case n = 6 using partition 6 = 3 + 3 and the corresponding block matrix
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.
Here rows 1, 2 and 3 are mutually incompatible, as are 4, 5 and 6. Choose a random row, say 3.
我们将排列写为数组:[2, 5, 6, 4, 3, 1]表示1 -> 2，2 -> 5，3 -> 6，...，这意味着块矩阵的行2将成为最终数组的第一行矩阵，行5将成为第二行，依此类推.
We will write a permutation as an array: [2, 5, 6, 4, 3, 1] meaning 1 -> 2, 2 -> 5, 3 -> 6, ... This means that row 2 of the block matrix will become the first row of the final matrix, row 5 will become the second row, and so on.
现在，让我们通过随机选择一行来构建合适的排列，例如3:
Now let's build a suitable permutation by choosing randomly a row, say 3:
-
p = [3, ...]
然后将在与3:4，5和6兼容的其余行中随机选择下一行.假设我们选择4:
The next row will then be chosen randomly among the remaining rows that are compatible with 3 : 4, 5and 6. Say we choose 4:
-
p = [3, 4, ...]
必须在1和2之间进行下一步选择，例如1:
Next choice has to be made among 1 and 2, for instance 1:
-
p = [3, 4, 1, ...]
以此类推:p = [3, 4, 1, 5, 2, 6].
将此置换应用于块矩阵，我们得到:
Applying this permutation to the block matrix, we get:
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]最终获得
Doing so, we manage to vertically isolate all non-zero entries. Same has to be done with the columns, for instance by using permutation p' = [6, 3, 5, 1, 4, 2] to finally get
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和分区6 = 2 + 2 + 2，遵循之前设置的构建规则可以导致p = [1, 3, 2, 4, ...].不幸的是，5和6不兼容，因此选择一个或另一个将使最后的选择成为不可能.我想我发现了所有导致死胡同的情况.我将用r表示剩余的选择集:
So this seems to work quite efficiently, but building these permutations needs to be done with caution, because one can easily be stuck: for instance, with n=6 and partition 6 = 2 + 2 + 2, following the construction rules set up earlier can lead to p = [1, 3, 2, 4, ...]. Unfortunately, 5 and 6 are incompatible, so choosing one or the other makes the last choice impossible. I think I've found all situations that lead to a dead end. I will denote by r the set of remaining choices:
-
p = [..., x, ?]，r = {y}与x和y不兼容 -
p = [..., x, ?, ?]，r = {y, z}，其中y和z均与x不兼容(无法选择) -
p = [..., ?, ?]，r = {x, y}与x和y不兼容(任何选择都会导致情况1) -
p = [..., ?, ?, ?]，r = {x, y, z}和x，y和z循环连续(选择x或z会导致情况2，选择y进入情况3) -
p = [..., w, ?, ?, ?]，r = {x, y, z}，其中xwy是3个循环(不能选择x或y，选择z会导致情况3) -
p = [..., ?, ?, ?, ?]，r = {w, x, y, z}，其中wxyz是一个4周期(任何选择都会导致情况4) -
p = [..., ?, ?, ?, ?]，r = {w, x, y, z}，其中xyz是3个周期(选择w将导致情况4，选择其他任何情况将导致情况4)
p = [..., x, ?],r = {y}withxandyincompatiblep = [..., x, ?, ?],r = {y, z}withyandzbeing both incompatible withx(no choice can be made)p = [..., ?, ?],r = {x, y}withxandyincompatible (any choice would lead to situation 1)p = [..., ?, ?, ?],r = {x, y, z}withx,yandzbeing cyclically consecutive (choosingxorzwould lead to situation 2, choosingyto situation 3)p = [..., w, ?, ?, ?],r = {x, y, z}withxwybeing a 3-cycle (neitherxnorycan be chosen, choosingzwould lead to situation 3)p = [..., ?, ?, ?, ?],r = {w, x, y, z}withwxyzbeing a 4-cycle (any choice would lead to situation 4)p = [..., ?, ?, ?, ?],r = {w, x, y, z}withxyzbeing a 3-cycle (choosingwwould lead to situation 4, choosing any other would lead to situation 4)
现在看来，以下算法提供了所有合适的排列:
Now it seems that the following algorithm gives all suitable permutations:
- 只要严格选择5个以上的数字，就可以在兼容的数字中随机选择.
- 如果还有5个数字可供选择:如果其余数字包含3个循环或4个循环，请中断该循环(即，选择属于该循环的数字).
- 如果还有4个数字可供选择:如果其余数字包含三个循环连续的数字，请选择其中一个.
- 如果还有3个数字可供选择:如果其余数字包含两个循环连续的数字，请选择其中一个.
我非常确定，这使我能够生成所有合适的排列，从而生成所有合适的矩阵.
I am quite sure that this allows me to generate all suitable permutations and, hence, all suitable matrices.
不幸的是，根据选择的分区，每个矩阵都会获得多次.
Unfortunately, every matrix will be obtained several times, depending on the partition that was chosen.
推荐答案
(以下是更新的测试结果，示例通过和代码段.)
您可以使用动态编程来计算每个状态产生的解的数量(比蛮力算法更有效)，并使用这些值(预先计算的值)来创建等概率的随机解.
You can use dynamic programming to calculate the number of solutions resulting from every state (in a much more efficient way than a brute-force algorithm), and use those (pre-calculated) values to create equiprobable random solutions.
考虑7x7矩阵的示例；一开始的状态是:
Consider the example of a 7x7 matrix; at the start, the state is:
0,0,0,0,0,0,0
表示有七个相邻的未使用列.在第一行中添加两个之后，状态可能是例如
meaning that there are seven adjacent unused columns. After adding two ones to the first row, the state could be e.g.:
0,1,0,0,1,0,0
有两列，现在其中有一个.将它们添加到第二行后，状态可能是例如
with two columns that now have a one in them. After adding ones to the second row, the state could be e.g.:
0,1,1,0,1,0,1
在填充三行之后，一列可能会有最多两行；这有效地将矩阵分为两个独立的区域:
After three rows are filled, there is a possibility that a column will have its maximum of two ones; this effectively splits the matrix into two independent zones:
1,1,1,0,2,0,1 -> 1,1,1,0 + 0,1
这些区域是独立的，这是指将相邻区域规则添加到不同区域时，no-adjacent-ones规则不起作用，并且区域的顺序对解决方案的数量也没有影响.
These zones are independent in the sense that the no-adjacent-ones rule has no effect when adding ones to different zones, and the order of the zones has no effect on the number of solutions.
为了将这些状态用作解决方案类型的签名，我们必须将它们转换为规范的表示法.首先，我们必须考虑一个事实，即其中只有1个的列在下一行可能不可用，因为它们在当前行中包含一个.因此，我们必须使用三元表示法来代替二进制表示法，例如:
In order to use these states as signatures for types of solutions, we have to transform them into a canonical notation. First, we have to take into account the fact that columns with only 1 one in them may be unusable in the next row, because they contain a one in the current row. So instead of a binary notation, we have to use a ternary notation, e.g.:
2,1,1,0 + 0,1
其中2表示此列已在当前行中使用(而不是该列中有2个).在下一步中，我们应该将两者重新转换为1.
where the 2 means that this column was used in the current row (and not that there are 2 ones in the column). At the next step, we should then convert the twos back into ones.
此外，我们还可以镜像单独的组，将它们放入其词典最小的符号中:
Additionally, we can also mirror the seperate groups to put them into their lexicographically smallest notation:
2,1,1,0 + 0,1 -> 0,1,1,2 + 0,1
最后，我们将不同的组从小到大进行排序，然后按字典顺序进行排序，这样，较大矩阵中的状态可能为:
Lastly, we sort the seperate groups from small to large, and then lexicographically, so that a state in a larger matrix may be e.g.:
0,0 + 0,1 + 0,0,2 + 0,1,0 + 0,1,0,1
然后，当计算每个状态得出的解的数量时，我们可以使用以每个状态的规范表示法为键的记忆.
Then, when calculating the number of solutions resulting from each state, we can use memoization using the canonical notation of each state as a key.
创建状态字典和每个状态的解法数仅需执行一次，并且较大矩阵的表也可以用于较小矩阵.
Creating a dictionary of the states and the number of solutions for each of them only needs to be done once, and a table for larger matrices can probably be used for smaller matrices too.
实际上，您将生成一个介于0和解决方案总数之间的随机数，然后对于每一行，您将查看可以从当前状态创建的不同状态，并查看唯一解决方案的数量每个都会生成，并查看哪个选项会导致与您随机生成的数字相对应的解决方案.
Practically, you'd generate a random number between 0 and the total number of solutions, and then for every row, you'd look at the different states you could create from the current state, look at the number of unique solutions each one would generate, and see which option leads to the solution that corresponds with your randomly generated number.
请注意，每个状态和相应的键只能出现在特定的行中，因此您可以将键存储在每行单独的词典中.
Note that every state and the corresponding key can only occur in a particular row, so you can store the keys in seperate dictionaries per row.
测试结果
使用未经优化的JavaScript进行的首次测试给出了非常有希望的结果.通过动态编程，现在需要花费一秒钟来计算10x10矩阵的解数，而蛮力算法要花几个小时(这是算法的一部分，只需要执行一次即可).带有签名和解数的字典的大小会随着大小的每一步逐渐接近2.5而增加；生成它的时间增长了大约3倍.
A first test using unoptimized JavaScript gave very promising results. With dynamic programming, calculating the number of solutions for a 10x10 matrix now takes a second, where a brute-force algorithm took several hours (and this is the part of the algorithm that only needs to be done once). The size of the dictionary with the signatures and numbers of solutions grows with a diminishing factor approaching 2.5 for each step in size; the time to generate it grows with a factor of around 3.
这些是创建的解决方案，状态，签名(字典的总大小)和每行签名的最大数量(每行最大的词典):
These are the number of solutions, states, signatures (total size of the dictionaries), and maximum number of signatures per row (largest dictionary per row) that are created:
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矩阵的字典如下:
The dictionary for a 5x5 matrix looks like this:
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个)解决方案，如下所示:
The total number of solutions is 16; if we randomly pick a number from 0 to 15, e.g. 13, we can find the corresponding (i.e. the 14th) solution like this:
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个解决方案.下一步是:
This tells us that the 14th solution is the 2nd solution of option 00101. The next step is:
state: 00101
options: 10010 01010
signature: 12102 02121
solutions: 1 3
这告诉我们第二个解决方案是选项01010的第一个解决方案.下一步是:
This tells us that the 2nd solution is the 1st solution of option 01010. The next step is:
state: 01111
options: 10100 10001 00101
signature: 11+12 1112 1+01
solutions: 2 1 0
这告诉我们第一个解决方案是选项10100的第一个解决方案.下一步是:
This tells us that the 1st solution is the 1st solution of option 10100. The next step is:
state: 11211
options: 01010 01001
signature: 1+1 1+1
solutions: 1 1
这告诉我们第一个解决方案是选项01010的第一个解决方案.最后一步是:
This tells us that the 1st solutions is the 1st solution of option 01010. The last step is:
state: 12221
options: 10001
与随机选择的数字13对应的5x5矩阵为:
And the 5x5 matrix corresponding to randomly chosen number 13 is:
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矩阵(生成字典需要花费一秒钟；完成后，它将在半毫秒内生成随机解):
And here's a quick'n'dirty code example; run the snippet to generate the signature and solution count dictionary, and generate a random 10x10 matrix (it takes a second to generate the dictionary; once that is done, it generates random solutions in half a millisecond):
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'而不是加号定界，并且在前一行中具有1的列标有'3'而不是a '2'.这显示了密钥如何以2×N位(用2填充)的整数形式存储在文件中.
The code snippet below shows the dictionary of signatures and solution counts for a matrix of size 10x10. I've used a slightly different signature format from the explanation above: the zones are delimited by a '2' instead of a plus sign, and a column which has a one in the previous row is marked with a '3' instead of a '2'. This shows how the keys could be stored in a file as integers with 2×N bits (padded with 2's).
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(""" + j + "": " + memo[i][j] + "<br>");
}
}
这篇关于在行和列中具有两个不相邻的非零的等概率随机平方二进制矩阵的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
