Complete Boolean Lattice对应的程序 *Q_n*

Question

我是数学系的一年级学生，我还没有编程 class。

我正在做一个项目，为了简化我的计算，最好实现一个程序来计算对应于完整布尔格的矩阵 Q_n ，它是一组从 1 到 n 的 n 个整数及其所有可能的子集。

例如，当 n=4 时，矩阵如下：

1;0;0;0;1;1;1;0;0;0;1;1;1;0;1

0;1;0;0;1;0;0;1;1;0;1;1;0;1;1

0;0;1;0;0;1;0;1;0;1;1;0;1;1;1

0;0;0;1;0;0;1;0;1;1;0;1;1;1;1

其中第一列对应于 {1,2,3,4} 的子集 {1}，第二列对应于 {1,2,3,4} 的子集 {2}，例如第 5 列对应于子集{1,2} 共 {1,2,3,4} 等等。

我的想法是首先创建相应大小的全零矩阵然后我不知道如何进行。请帮我出出主意。

Answer 1

itertools 模块让这一切变得简单。这是一种方法：

import itertools

def subset_matrix(n):
    A = [[0]*pow(2,n) for _ in range(n)]
    j = 0
    for k in range(n+1):
        for c in itertools.combinations(range(n),k):
            for i in c:
                A[i][j] = 1
            j += 1
    return A

#for example:

A = subset_matrix(4)
for row in A:
    print(row)

输出：

[0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1]
[0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1]
[0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1]
[0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1]