0
$\begingroup$

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 (I'm using Motion Canvas). Having a pseudocode would be wonderful however I really appreciate any pointer that can help me in my struggle!

So far, 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!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It took me a while to understand that your goal is: write an algorithm to create a random lattice on $n$ elements. Of course, to make it a specific problem you need to describe what distribution you want to sample from. Certainly a uniform distribution would be very hard to achieve (because there is nothing like a "structure theorem" for finite lattices...) $\endgroup$
    – Sam Hopkins
    Commented Jun 11, 2023 at 2:24
  • $\begingroup$ Oh, I don't actually mind the distribution because all know that in all of them there is a chance for lattice to pop up :) And yes, indeed my goal is to create a random lattice on n elements :P $\endgroup$
    – Luisz
    Commented Jun 11, 2023 at 2:33

1 Answer 1

Reset to default
1
$\begingroup$

Sage (https://www.sagemath.org/) has code to produce a random lattice on $n$ elements: see https://doc.sagemath.org/html/en/reference/combinat/sage/combinat/posets/poset_examples.html#sage.combinat.posets.poset_examples.Posets.RandomLattice

I have no idea what algorithm it uses or what distribution it aims to sample from, but it's a start.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh my god, thank you, Sam! You're a saint! $\endgroup$
    – Luisz
    Commented Jun 11, 2023 at 2:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .