Uniform random generation of StandardTableau of a given size

[rodgzilla]

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.

CC: @VivianePons @tscrim @darijgr @sagetrac-sage-combinat @nthiery

Component: combinatorics

Keywords: StandardTableaux, random, combinat

Author: Grégory Châtel

Branch/Commit: 3247ee5

Reviewer: Darij Grinberg

Issue created by migration from https://trac.sagemath.org/ticket/17233

[rodgzilla]

Commit: 3afe723

[rodgzilla]

Branch: public/combinat/tableaux-random-17233

[rodgzilla]

New commits:

3afe723

First commit overwritting the method random_element of StandardTableaux_size.

[rodgzilla]

comment:2

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.

[tscrim]

comment:3

You mark it as # random.

[darijgr]

comment:4

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 catch-all 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 replacing Permutation(...) by sage.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.

[tscrim]

comment:5

Replying to @darijgr:

• 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.

[darijgr]

comment:6

Oops, I think I was looking at some outdated version of the file on the internet.

[darijgr]

comment:8

More minor comments:

• "couple" should be "pair" in mathematical usage.

• You are using Permutations(self.size).random_element()[:fixed_point_number] to generate a random k-element subset of {1, 2, ..., n} (if I understand you correctly -- otherwise, please correct me!). I think you can just as well do sage.misc.prandom.sample(range(1, n+1), k), which is the method that is internally used when you call Permutations(self.size).random_element().

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

39413ba

Minor improvement on the documentation and on the way the method

[sagetrac-git]

Changed commit from 3afe723 to 39413ba

[sagetrac-git]

Changed commit from 39413ba to d8ddf27

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

d8ddf27

Improvement on doctest.

[darijgr]

Reviewer: Darij Grinberg

[sagetrac-git]

Changed commit from d8ddf27 to c8de1be

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

c8de1be

doc only so far

[sagetrac-git]

Changed commit from c8de1be to 74b18f4

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

74b18f4

review

[darijgr]

comment:15

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

[sagetrac-git]

Changed commit from 74b18f4 to 67e189f

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

67e189f

Put the import at the beggining of the method.

[vbraun]

comment:18

PDF docs don't bulid (lfoor -> lfloor)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3247ee5

typo fixed

[sagetrac-git]

Changed commit from 67e189f to 3247ee5

[vbraun]

Changed branch from public/combinat/tableaux-random-17233 to 3247ee5