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

Status badges

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

  • Branch set to public/combinat/composition-random-17242
  • Commit set to c2ddd33adbf47f86a6a3db60f6f84bec64989c5a

New commits:

c2ddd33First commit overwritting the method random_element of Compositions_n.

comment:2 Changed 7 years ago by git

  • Commit changed from c2ddd33adbf47f86a6a3db60f6f84bec64989c5a to 2470bbf9bbfcab09c8645d9ec36c64467bc75b42

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

2470bbfFixing a format problem with the documentation.

comment:3 Changed 7 years ago by g.chatel

  • Cc chapoton added
  • Status changed from new to needs_review

comment:4 Changed 7 years ago by chapoton

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 darij

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 git

  • Commit changed from 2470bbf9bbfcab09c8645d9ec36c64467bc75b42 to d6ca32abfa3d922d2d147f54255de05459946847

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

6539c20Putting the deleted line back.
d6ca32aCleaning up the code.

comment:7 Changed 7 years ago by darij

  • Status changed from needs_review to positive_review

comment:8 Changed 7 years ago by darij

Welldone; it's positive_review then.

comment:9 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work

Reviewer name

comment:10 Changed 7 years ago by darij

  • Reviewers set to Darij Grinberg
  • Status changed from needs_work to positive_review

comment:11 Changed 7 years ago by vbraun

  • Status changed from positive_review to needs_work

Doctests failure in src/sage/combinat/composition_signed.py

comment:12 Changed 7 years ago by git

  • Commit changed from d6ca32abfa3d922d2d147f54255de05459946847 to 39391763e5a5734c8b46c20b0f46369575003551

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

3939176random doctest is random

comment:13 Changed 7 years ago by darij

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

  • Branch changed from public/combinat/composition-random-17242 to 39391763e5a5734c8b46c20b0f46369575003551
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.