Opened 8 years ago

Closed 6 years ago

#9890 closed defect (fixed)

A proper random_element() method for PerfectMatchings

Reported by: ncohen Owned by: sage-combinat
Priority: major Milestone: sage-5.10
Component: combinatorics Keywords:
Cc: nthiery, fhivert Merged in: sage-5.10.beta5
Authors: Nathann Cohen Reviewers: Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

At the moment, the method random_element() from PerfectMatchings? computes a random matching by picking a random integer between 0 and the number of matchings on n elements, then (I presume) enumerating all the matchings according to some ordering until the kth has been computed. This is impressively useless.

sage: %timeit PerfectMatchings(12).random_element()
5 loops, best of 3: 1.5 s per loop

By the way, I was not able to write a method to obtain the list of pairs describing the matching from an PerfectMatching? object.. I don't understand how this class is written, and I have no idea why it needs to be so complicated (but it would be nice to add it to this ticket during the review, if someone gets how it works).

The method random_element (and also an_element) both raise an exception when the set of elements is EMPTY. I also fixed the doctests.

(I don't even get why you can build a PerfectMatchings? class on an odd number of elements in the first place)

I expect this ticket could be heavily modified during review, but there is a problem with these classes at the moment.

Nathann

Attachments (2)

trac_9890.patch (2.5 KB) - added by ncohen 6 years ago.
trac_9890_review.patch (32.5 KB) - added by chapoton 6 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 6 years ago by ncohen

  • Cc nthiery fhivert added

I forgot to click on needs_review three years ago T_T

Nathann

comment:2 Changed 6 years ago by ncohen

  • Status changed from new to needs_review

Patch updated ! On the way, I also fixed this "small problem" :

sage: PerfectMatchings(3).an_element()
[(1, 2)]

Nathann

Changed 6 years ago by ncohen

comment:3 follow-up: Changed 6 years ago by chapoton

hello,

looks good to me.

I have taken the opportunity to make a complete cosmetic clean-up of the file (using pep8 and pyflakes)

if my review patch is ok for you, you can set a positive review

Changed 6 years ago by chapoton

comment:4 in reply to: ↑ 3 Changed 6 years ago by ncohen

  • Authors set to Nathann Cohen
  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

I have taken the opportunity to make a complete cosmetic clean-up of the file (using pep8 and pyflakes)

if my review patch is ok for you, you can set a positive review

Okayyyyyyy ! Good to go, then :-)

By the way, how do you use pep8 and pyflakes ? Do you run them externally on files or do you have a way to use them ?

Nathann

comment:5 Changed 6 years ago by chapoton

Yes, I just run them on the *.py files. Pyflakes is more important, as it finds missing imports and unused variables. Pep8 is much more for the cosmetic, but can check that raise statements are in python3 syntax and find other deprecated syntax.

comment:6 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.10.beta5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.