Opened 7 years ago
Closed 7 years ago
#17233 closed enhancement (fixed)
Uniform random generation of StandardTableau of a given size
Reported by:  g.chatel  Owned by:  gchatel 

Priority:  major  Milestone:  sage6.4 
Component:  combinatorics  Keywords:  StandardTableaux, random, combinat 
Cc:  VivianePons, tscrim, darij, sagecombinat, nthiery  Merged in:  
Authors:  Grégory Châtel  Reviewers:  Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  3247ee5 (Commits, GitHub, GitLab)  Commit:  3247ee5accbcd22ebb640c95c3bf37bdf41fb0dd 
Dependencies:  Stopgaps: 
Description
I am overwritting the default random_element method of the StandardTableaux_size class to implement an efficient way to compute a random standard tableau.
As explained in the documentation, we use the fact that standard tableau are in bijection with involution.
Change History (21)
comment:1 Changed 7 years ago by
 Branch set to public/combinat/tableauxrandom17233
 Commit set to 3afe72304d59aa71dd7c212ea7f3a20a49245821
comment:2 Changed 7 years ago by
 Cc tscrim darij sagecombinat nthiery added
This code is finished and seems to be working. How can I add doctest and examples although the output is random. For this reason, I didn't put a "need review" yet but anyone is welcome to start.
comment:3 Changed 7 years ago by
You mark it as # random
.
comment:4 followup: ↓ 5 Changed 7 years ago by
Just a few comments:
 The doc should start with a brief description of what the code does, not what theorems it uses. If your algorithm gives a uniform random permutation, then it should say so explicitly.
 Do not use generic catchall constructors such as
Permutation(...)
. These ducktype the input to guess which form you are giving the permutation in. This is great for interactive use, but in your code you know what form you are giving already  it is the cycle form. So you can save some time and remove a source of possible bugs by replacingPermutation(...)
bysage.combinat.permutation.from_cycles(...)
.
 Is this:
PerfectMatchings(set(range(1, self.size + 1))  set(fixed_point_positions)).random_element()
actually efficient? I am asking because I don't see a random method in perfect_matchings.py, but I might not be looking in the right place.
comment:5 in reply to: ↑ 4 Changed 7 years ago by
Replying to darij:
 Is this:
PerfectMatchings(set(range(1, self.size + 1))  set(fixed_point_positions)).random_element()actually efficient? I am asking because I don't see a random method in perfect_matchings.py, but I might not be looking in the right place.
There is a random_element
in perfect_matchings.py
; although it calls Permutations(n).random_element()
which looks like it's fast.
comment:6 Changed 7 years ago by
Oops, I think I was looking at some outdated version of the file on the internet.
comment:7 Changed 7 years ago by
 Component changed from PLEASE CHANGE to combinatorics
comment:8 Changed 7 years ago by
More minor comments:
 "couple" should be "pair" in mathematical usage.
 You are using
Permutations(self.size).random_element()[:fixed_point_number]
to generate a randomk
element subset of{1, 2, ..., n}
(if I understand you correctly  otherwise, please correct me!). I think you can just as well dosage.misc.prandom.sample(range(1, n+1), k)
, which is the method that is internally used when you callPermutations(self.size).random_element()
.
comment:9 Changed 7 years ago by
 Commit changed from 3afe72304d59aa71dd7c212ea7f3a20a49245821 to 39413ba27f9bfdda079c8e06ccaf1ef60940f67d
Branch pushed to git repo; I updated commit sha1. New commits:
39413ba  Minor improvement on the documentation and on the way the method

comment:10 Changed 7 years ago by
 Commit changed from 39413ba27f9bfdda079c8e06ccaf1ef60940f67d to d8ddf27e1929ec8c493ac65867a74a575722d742
Branch pushed to git repo; I updated commit sha1. New commits:
d8ddf27  Improvement on doctest.

comment:11 Changed 7 years ago by
 Status changed from new to needs_review
comment:12 Changed 7 years ago by
 Reviewers set to Darij Grinberg
comment:13 Changed 7 years ago by
 Commit changed from d8ddf27e1929ec8c493ac65867a74a575722d742 to c8de1be8f6577a1ddf9435a092fc58adb75fab34
Branch pushed to git repo; I updated commit sha1. New commits:
c8de1be  doc only so far

comment:14 Changed 7 years ago by
 Commit changed from c8de1be8f6577a1ddf9435a092fc58adb75fab34 to 74b18f4ecf8c2ba0109a4f9e79ac701ddbd4c5a3
Branch pushed to git repo; I updated commit sha1. New commits:
74b18f4  review

comment:15 Changed 7 years ago by
Here's my review patch. If you are fine with it, please set this to positive_review.
binomial
should be imported from sage.rings.arith
rather than from sage.functions.other
when you just want to compute binomial coefficients of integers. Check this:
sage: %timeit binomial(13, 5) # This is the one from sage.functions.other 10000 loops, best of 3: 61.1 µs per loop sage: %timeit sage.rings.arith.binomial(13, 5) 100000 loops, best of 3: 5.6 µs per loop sage: %timeit binomial(54, 23) 10000 loops, best of 3: 61.7 µs per loop sage: %timeit sage.rings.arith.binomial(54, 23) 100000 loops, best of 3: 6.16 µs per loop
comment:16 Changed 7 years ago by
 Commit changed from 74b18f4ecf8c2ba0109a4f9e79ac701ddbd4c5a3 to 67e189febcbf4899f003788d073df06683a05089
Branch pushed to git repo; I updated commit sha1. New commits:
67e189f  Put the import at the beggining of the method.

comment:17 Changed 7 years ago by
 Status changed from needs_review to positive_review
comment:18 Changed 7 years ago by
 Status changed from positive_review to needs_work
PDF docs don't bulid (lfoor > lfloor)
comment:19 Changed 7 years ago by
 Commit changed from 67e189febcbf4899f003788d073df06683a05089 to 3247ee5accbcd22ebb640c95c3bf37bdf41fb0dd
Branch pushed to git repo; I updated commit sha1. New commits:
3247ee5  typo fixed

comment:20 Changed 7 years ago by
 Status changed from needs_work to positive_review
comment:21 Changed 7 years ago by
 Branch changed from public/combinat/tableauxrandom17233 to 3247ee5accbcd22ebb640c95c3bf37bdf41fb0dd
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
First commit overwritting the method random_element of StandardTableaux_size.