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

Priority:  major  Milestone:  sage6.4 
Component:  combinatorics  Keywords:  composition, combinatorics, random 
Cc:  VivianePons, tscrim, darij, sagecombinat, nthiery, chapoton  Merged in:  
Authors:  Grégory Châtel  Reviewers:  Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  3939176 (Commits, GitHub, GitLab)  Commit:  39391763e5a5734c8b46c20b0f46369575003551 
Dependencies:  Stopgaps: 
Description
I am overwritting the default random_element method of the Composition_n class to implement an efficient way to compute a random composition.
As explained in the documentation, I use the fact that composition of size n are in bijection with binary words of size n starting with a 1.
Change History (14)
comment:1 Changed 7 years ago by
 Branch set to public/combinat/compositionrandom17242
 Commit set to c2ddd33adbf47f86a6a3db60f6f84bec64989c5a
comment:2 Changed 7 years ago by
 Commit changed from c2ddd33adbf47f86a6a3db60f6f84bec64989c5a to 2470bbf9bbfcab09c8645d9ec36c64467bc75b42
Branch pushed to git repo; I updated commit sha1. New commits:
2470bbf  Fixing a format problem with the documentation.

comment:3 Changed 7 years ago by
 Cc chapoton added
 Status changed from new to needs_review
comment:4 Changed 7 years ago by
You have deleted one line in some other place in the file. (to see where, click on the green link in the branch field on top of this page). Please put it back.
Also, please gather the imports at the begininng of the code. Otherwise, seems ok.
comment:5 Changed 7 years ago by
I have not done any benchmarks, but I bet that
[sage.misc.prandom.choice([0,1]) for _ in range(self.n  1)]
is faster than FiniteWords_length_k_over_OrderedAlphabet(A, length = self.n  1).random_element()
(and, besides, works for n = 0 as well).
comment:6 Changed 7 years ago by
 Commit changed from 2470bbf9bbfcab09c8645d9ec36c64467bc75b42 to d6ca32abfa3d922d2d147f54255de05459946847
comment:7 Changed 7 years ago by
 Status changed from needs_review to positive_review
comment:8 Changed 7 years ago by
Welldone; it's positive_review then.
comment:10 Changed 7 years ago by
 Reviewers set to Darij Grinberg
 Status changed from needs_work to positive_review
comment:11 Changed 7 years ago by
 Status changed from positive_review to needs_work
Doctests failure in src/sage/combinat/composition_signed.py
comment:12 Changed 7 years ago by
 Commit changed from d6ca32abfa3d922d2d147f54255de05459946847 to 39391763e5a5734c8b46c20b0f46369575003551
Branch pushed to git repo; I updated commit sha1. New commits:
3939176  random doctest is random

comment:13 Changed 7 years ago by
 Status changed from needs_work to positive_review
Good point; that file had a random doctest not marked as random. I am wondering if we can have a script that automatically warns of such things?
comment:14 Changed 7 years ago by
 Branch changed from public/combinat/compositionrandom17242 to 39391763e5a5734c8b46c20b0f46369575003551
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
First commit overwritting the method random_element of Compositions_n.