Mark Gritter (markgritter) wrote,
Mark Gritter

Implementing a Simple Partial Order

The partial order whose Hasse diagram is shown on the left represents a particular piece of "business logic" I'm working on. What I'm interested in is efficiently calculating the join of a (usually small) set of values. For example, join(0,Y) = Y; join(Y,N) = P; join(M,P) = M; join(0,Y,Y,Y)=Y.

How would you represent the join operation in code, in such a way that the simple structure of the poset is not obscured, but the code is reasonably efficient? Our current implementation is a nest of 'if' statements that works but doesn't cleanly express the structure--- and I suspect it could be shorter!

Is there a general strategy that works well here, for more complicated orders? Or do you end up building lookup tables?

Bonus geekery: the number of partial orders with N elements.

Tags: geek, mathematics, partial orders, programming
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.