Search code examples
pythonmatrixsubsetadjacency-matrixboolean-algebra

Program corresponding to Complete Boolean Lattice *Q_n*

I am first year student of Math faculty, and I didn't have programming class yet.

I am working on a project and to simplify my calculations it would be nice to implement a program that would calculate a matrix corresponding to the complete boolean lattice Q_n, which is a set of n integers from 1 to n and all of its possible subsets.

For example, when n=4 the matrix would be the following:

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

where first column correspond to the subset {1} of {1,2,3,4}, second column to subset {2} of {1,2,3,4}, column 5 for example to subset {1,2} of {1,2,3,4} and so on.

My idea was to create first all zero matrix of the corresponding size and then I do not know how to proceed. Please help me to get ideas.

Solution

  • The itertools module makes this easy. Here is one way:

    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)

    Output:

    [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]