Opened 7 years ago

Closed 7 years ago

# Uniform random generation of StandardTableau of a given size

Reported by: Owned by: g.chatel gchatel major sage-6.4 combinatorics StandardTableaux, random, combinat VivianePons, tscrim, darij, sage-combinat, nthiery Grégory Châtel Darij Grinberg N/A 3247ee5 3247ee5accbcd22ebb640c95c3bf37bdf41fb0dd

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

### comment:1 Changed 7 years ago by g.chatel

• Branch set to public/combinat/tableaux-random-17233
• Commit set to 3afe72304d59aa71dd7c212ea7f3a20a49245821

New commits:

 ​3afe723 `First commit overwritting the method random_element of StandardTableaux_size.`

### comment:2 Changed 7 years ago by g.chatel

• Cc tscrim darij sage-combinat 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 tscrim

You mark it as `# random`.

### comment:4 follow-up: ↓ 5 Changed 7 years ago by darij

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

### comment:5 in reply to: ↑ 4 Changed 7 years ago by tscrim

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

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

### comment:7 Changed 7 years ago by tscrim

• Component changed from PLEASE CHANGE to combinatorics

### comment:8 Changed 7 years ago by darij

• "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()`.

### comment:9 Changed 7 years ago by git

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

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

• Status changed from new to needs_review

### comment:12 Changed 7 years ago by darij

• Reviewers set to Darij Grinberg

### comment:13 Changed 7 years ago by git

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

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

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
```
Last edited 7 years ago by darij (previous) (diff)

### comment:16 Changed 7 years ago by git

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

• Status changed from needs_review to positive_review

### comment:18 Changed 7 years ago by vbraun

• Status changed from positive_review to needs_work

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

### comment:19 Changed 7 years ago by git

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

• Status changed from needs_work to positive_review

### comment:21 Changed 7 years ago by vbraun

• Branch changed from public/combinat/tableaux-random-17233 to 3247ee5accbcd22ebb640c95c3bf37bdf41fb0dd
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.