小编Chr*_*ngs的帖子

如果有人能指出我允许我的算法,那会很棒:

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 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 …