python - 生成 n X n 个非同构二元矩阵的算法

Question

#include <stdio.h>
int main()
{
    for (int i = 0; i < 1 << 4; i++)
    {
        printf("%d %d\n", (i >> 0) & 1, (i >> 1) & 1);
        printf("%d %d\n", (i >> 2) & 1, (i >> 3) & 1);
        printf("\n");
    }
    return 0;
}

n×n的二元矩阵有2^(n^2)种可能，同构是指棋盘的旋转和反射的对称操作算作1。
例如有6个非同构2 X 2矩阵，

[0 0] [0 0] [0 0] [0 1] [0 1] [1 1]
[0 0] [0 1] [1 1] [1 0] [1 1] [1 1]。

在 python 或 C 中生成这样的 n X n 二进制矩阵的有效方法是什么？

Answer 1

尝试回答的最佳方法是计算 3x3 的组合数量。

您必须区分 3 类细胞:

1. 旋转/反射不变的中心
2. 4 条边
3. 4个角

由于中心是不变的，它是完全独立的，所以我们必须将不包括中心的解的数量乘以2

x x x     x x x
x 0 x  +  x 1 x
x x x     x x x

有 6 种不同的角组合:

0 x 0   1 x 0   1 x 1   1 x 0   1 x 1   1 x 1
x   x   x   x   x   x   x   x   x   x   x   x
0 x 0   0 x 0   0 x 0   0 x 1   1 x 0   1 x 1

边缘也一样。我们现在可以检查边缘和角的组合，为此我将表格的 block 数设置为 1。
请注意，放置 1 或放置 0 是同一个问题，因此我们的行和列是对称的...
我不提供组合的详细信息，只提供我发现的不同组合的数量:

x   0 1 2 3 4

0   1 1 2 1 1
1   1 2 4 2 1
2   2 4 7 4 2
3   1 2 4 2 1
4   1 1 2 1 1

所以这是 51，与中心组合时乘以 2，因此有 102 种组合。

现在我们知道了该系列的前 3 个术语，我们可以继续在 OEIS 上搜索匹配的 2,6,102。

https://oeis.org/search?q=2%2C6%2C102&sort=&language=french&go=Chercher

我们找到https://oeis.org/A054247

Number of n X n binary matrices under action of dihedral group of the square D_4

我不会再继续下去，这个问题很难在这里给出完整的答案，但至少你现在有了可以自己查找的链接......