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: sage-6.4
Component: combinatorics Keywords: StandardTableaux, random, combinat
Cc: VivianePons, tscrim, darij, sage-combinat, 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:

Status badges

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

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

New commits:

3afe723First 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: Changed 7 years ago by darij

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.

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

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

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().

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:

39413baMinor 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:

d8ddf27Improvement 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:

c8de1bedoc 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:

74b18f4review

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:

67e189fPut 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:

3247ee5typo 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.