提出高效生成二值幻方的算法，支持矩形和并行计算。
Efficient Generation of Binary Magic Squares
- 基于归纳法设计简单算法，保证生成正确二值幻方。
- 证明算法在理论复杂度上最优，且可扩展至非方阵情形。
- 开源双版本实现，含GPU加速并行生成能力。
我们提出一种简单算法用于生成二值幻方（BMS），即行和列和均相等的二进制方阵。通过归纳法证明该算法始终能生成有效BMS，且具有最优理论复杂度。随后将研究拓展至非方阵二值幻方，形式化了行和与列和存在的条件，并证明原算法稍作修改即可严格生成此类矩阵。最后，我们公开发布两个Python实现版本，其中包含利用GPU加速并行生成多个BMS的功能。
原文摘要 · Abstract (English)
We propose a simple algorithm for generating Binary Magic Squares (BMS), i.e., square binary matrices where the sum of all rows and all columns are equal. We show by induction that our algorithm always returns valid BMS with optimal theoretical complexity. We then extend our study to non-square Binary Magic Squares, formalize conditions on the sum of rows and columns for these BMS to exist, and show that a slight variant of our first algorithm can generate provably generate them. Finally, we publicly release two implementations of our algorithm as Python packages, including one that can generate several BMS in parallel using GPU acceleration.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。