每行和每列有两个不相邻的非零点的等概率随机二元矩阵的算法 [英] 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 ->->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}withx和y不兼容p = [..., x, ?, ?],r = {y, z}withy和z与x不兼容(无法选择)p = [..., ?, ?],r = {x, y}withx和y不兼容(任何选择都会导致情况 1)p = [..., ?, ?, ?],r = {x, y, z}withx,y和z循环连续(选择x或z会导致情况 2，选择y到情况 3)p = [..., w, ?, ?, ?],r = {x, y, z}withxwy> 是一个 3-cycle(x和y都不能选择，选择z会导致情况 3)p = [..., ?, ?, ?, ?],r = {w, x, y, z}withwxyz是一个 4-cycle(任何选择都会导致情况 4)p = [..., ?, ?, ?, ?],r = {w, x, y, z}withxyz是一个 3-cycle(选择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 个 1 的列在下一行可能无法使用，因为它们在当前行中包含一个 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 个).在下一步中，我们应该将两个转换回一个.
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
(使用 C++ 获得的附加结果，使用一个简单的 128 位整数实现.要计算状态，必须使用每个状态作为单独的签名来运行代码，而我无法为最大的尺寸.)
例子
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
<小时>
这是一个简单的代码示例；运行代码片段以生成签名和解决方案计数字典，并生成一个随机的 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"而不是加号分隔，前一行中有一个的列用3"而不是"'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屋！
