#17036: RandomPoset does not use set_random_seed
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: defect | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Jori Mäntysalo | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/randomposet_does_not_use_set_random_seed|
d55fe67004c67e7d4a813dda50a3a2d3eecaa9d9
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by ncohen):
My mistake. I just looked at the code of `RandomPoset`, and the call to
`random()` definitely isn't the critical part.
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 just say this in case we want to change it later. I will give a positive
review to that patch in a second.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17036#comment:9>
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.
