Zach Langley
Reputation
270
Top tag
Next privilege 300 Rep.
Create tags
Badges
1 10
Newest
Impact
~817 people reached

• 0 helpful flags
• 7 votes cast

# 9 Comments

 Aug10 comment Generating Linear Extensions of a Partial Order Although it's not as concise, I'm accepting this answer because its performance trumps the others'. Aug8 comment How to perform a breadth-first traversal of an expression? @Mr.Wizard Yes, that is a breadth-first traversal. Aug7 comment Word Squares and Beyond @R.M Thanks, definitely looks interesting! Aug6 comment Generating Linear Extensions of a Partial Order Ohhh, I see. Nice! I didn't think to use integer programming for this. This is certainly the most efficient solution so far. Aug6 comment Generating Linear Extensions of a Partial Order Can you explain the fourth constraint? Aug6 comment Generating Linear Extensions of a Partial Order @alancalvitti $\Omega$ is an asymptotic lower bound. Think of $O$ as $\le$, $o$ as $<$, and $\Omega$ as $\ge$. (The analogy falls apart for some pairs of functions which are neither $O$ nor $\Omega$ of each other.) Aug6 comment Word Squares and Beyond @Verbeia I haven't tried anything yet. I'm not as interested in having a solution to the problem as I am in seeing how expert Mathematica users would approach it. As you pointed out, this problem becomes quickly intractable, so I'm not looking for solutions whose asymptotic running time remarkable, but rather clever ways to utilize Mathematica's toolbox to solve the problem with not too many lines of code. Aug5 comment Generating Linear Extensions of a Partial Order Interestingly, the pattern matching seems to be much faster than this. Try, for example, with linearExtensions[{a, b, c, d, e, f, g, h, i}, {{a, c}, {b, c}, {f, g}, {g, e}, {d, a}, {h, i}, {i, d}, {g, h}}]. Aug4 comment Generating Linear Extensions of a Partial Order Nice! I didn't realize Subsets preserved order. Is there no nicer way to determine if a list is a subset of another than what you're doing here?