#17048: Faster Posets.RandomPoset
-----------------------------+---------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: new
Priority: minor | Milestone: sage-wishlist
Component: combinatorics | Keywords:
Merged in: | Authors:
Reviewers: | Report Upstream: N/A
Work issues: | Branch:
Commit: | Dependencies:
Stopgaps: |
-----------------------------+---------------------------------
Nathann Cohen wrote on another ticket:
"This code could be seriously rewritten, though. In two different ways:
1) Assume from the start that 0,...,n-1 is a linear extension, and only
add edges i,j with i<j. With this you don't have to call
`is_directed_acyclic` every second (and this is the bottleneck of the
implementation). At the end, relabel everything randomly so that the
linear extension is random, too
2) Work directly on the Hasse Diagram. Build the random Poset on n
elements from a poset on n-1 elements:
Consider all minimal elements `m_1,...m_c` of the previous digraph and add
the edges `m_i,n` with probability `p`. If some edge `m_i` was not added,
consider the immediate predecessors of `m_i` and do the same with them.
This second way to build them benefits from the transitivity of posets.
The last algorithm was mentionned by Florent and Nicolas to which I asked
the question. They seemed to think that this generation of random posets
was not standard, and that we could change it a bit if we like, i.e.
without caring if by changing the algorithm we change the distribution of
posets. It seems that it is only there to provide random posets for
computer tests, with no specific property in mind."
I add this on wishlist-milestone, so that I don't forget it totally. I'm
not going to code this at least for release 6.4.
--
Ticket URL: <http://trac.sagemath.org/ticket/17048>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
