生成随机二进制矩阵

Question

我希望生成10,000个随机的二进制矩阵，该矩阵每行和每列有与给定二进制矩阵相同数量的1。

该矩阵大约为500 x 10,000。其中约有2,000,000个1。没有零行或零列。

我的当前方法将二进制矩阵转换为二分邻接矩阵，并执行1,000,000次随机边交换以保证随机性。这需要13,000秒才能生成1个矩阵。我使用修改过的networkx的double_edge_swap函数编写python代码。

是否有更有效的方法来生成这样的矩阵？

- Jonathan Lu

---

我正在寻找这个问题的名称。它是离散层析成像的主要问题，“处理从其水平和垂直线段和中重建二进制图像”，对于二维情况（成对非平行晶格方向），该问题在P内。了解需要10,000个随机选择的可能重建是很有趣的。 - Dan D.

你应该指定需要哪种特定的分布，因为不同的方法可能会给出略微不同的分布。 - Veedrac

这取决于您是否只想提高生成矩阵的效率，好的解决方案将是从Python调用c（）函数来生成矩阵。 - ElConrado

Answer 1

我认为您可以首先建立这种矩阵的特殊情况，然后使用 numpy.shuffle 进行打乱：

row_sum = 2
col_sum = 1
arr     = np.zeros((5, 10))
#generate a special case, with given row_sum and col_sum
for i in range(row_sum):
    arr.ravel()[i::arr.shape[1]+row_sum] = 1
arr

Out[84]: 
array([[ 1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  1.,  1.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  1.,  1.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,  1.]])

np.random.shuffle(arr)
#np.random.shuffle(arr.T) to shuffle the columns
arr
Out[89]: 
array([[ 0.,  0.,  0.,  0.,  1.,  1.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  1.,  1.],
       [ 0.,  0.,  1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  0.,  0.,  0.,  1.,  1.,  0.,  0.],
       [ 1.,  1.,  0.,  0.,  0.,  0.,  0.,  0.,  0.,  0.]])

arr.sum(1) #row sums
Out[90]: array([ 2.,  2.,  2.,  2.,  2.])

arr.sum(0) #col sums
Out[91]: array([ 1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.,  1.])

- CT Zhu

---

如果可能的话，我建议有点“懒惰”。我们可以通过定义一系列行号（例如[2, 4, 1, 3, 0]）来生成一个新矩阵，并在需要进行赋值时转换为完整的np.array，或者使用某种形式的“更改历史记录”（但我不确定numpy是否能够处理动态大小的数组）。 - u354356007

动态的 numpy 数组可能行不通，之前已经讨论过了 https://dev59.com/J2w05IYBdhLWcg3w6GAw 。我猜想一个可能会选择 Fortran 或者 C 来实现动态数组。但是等等，这已经不再是一个 懒惰 的解决方案了， :) - CT Zhu

如果行是 [6, 5, 6, 4, 6, 7, 4, 5, 4, 4]，列是 [3, 6, 5, 7, 2, 8, 3, 3, 4, 10] 而不是常数，那该怎么办？即使您有一个解决方案，简单地洗牌并不总能产生其他解决方案。 - Dan D.

Answer 2

尝试过这个，它有效

np.mod(np.random.permutation(N*N).reshape(N,N),2)

例子：

>>> np.mod(np.random.permutation(4*4).reshape(4,4),2)  
array([[0, 0, 0, 1],
      [1, 1, 1, 0],
      [1, 0, 0, 1],
      [0, 1, 1, 0]])
>>> np.mod(np.random.permutation(4*4).reshape(4,4),2)  
array([[0, 0, 0, 1],
      [1, 1, 0, 0],
      [1, 1, 1, 1],
      [0, 0, 1, 0]])

- codenio