Algorithm to generate a lattice (Poset) from a positive integer parameter

54 Views Asked by At

As the title suggests, I've been trying to create a lattice (Poset) generator from a positive integer parameter n which represents the number of nodes.

The reason why I'm trying to do this is because I want to create hasse diagrams of lattices for fun, but doing so by hand is a very tiring process and i want an algorithm to help me draw my lattices. Preferably in Typescript where I can plug them in Motion Canvas, although having a pseudocode would also be great and an explanation as to why the algorithm works would be super!

However, I've only been able to create join semilattice generator and I honestly haven't found any useful resources online that could help me.

Here's the code for the curious (not sure how much this will help, though):

from random import randint
from itertools import combinations

# join
def build_semilattice(n):
    lattice = [[] for i in range(n)]
    batches = [[0]] # add the least
    step = 1
    while step < n-1: # ou step != n + 1
        k = randint(step,n-2)
        batches.append([i for i in range(step, k+1)])
        step = k + 1
    batches.append([n-1]) # add the greatest
    print(batches)
    for batch in range(len(batches) - 1):
        for a,b in combinations(batches[batch], 2):
            k = randint(batches[batch + 1][0], batches[batch + 1][-1])
            lattice[a].append(k), lattice[b].append(k)
    return lattice

print(build_semilattice(10))

Thank you very much for your answer!

0

There are 0 best solutions below