Opened 10 years ago
Closed 8 years ago
#12867 closed defect (fixed)
random_element for Words is broken
Reported by:  Alex Ghitza  Owned by:  Sage Combinat CC user 

Priority:  major  Milestone:  sage6.3 
Component:  combinatorics  Keywords:  
Cc:  Sage Combinat CC user, Vincent Delecroix, Franco Saliola, Sébastien Labbé  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  3f13460 (Commits, GitHub, GitLab)  Commit:  3f13460e1441bfaf2d5539262add1ad056f9fb7d 
Dependencies:  Stopgaps: 
Description
sage: W = Words(5) sage: W.random_element()  TypeError Traceback (most recent call last) /home/ghitza/<ipython console> in <module>() /scratch/ghitza/sage5.0.beta10/local/lib/python2.7/sitepackages/sage/combinat/combinat.pyc in __random_element_from_unrank(self) 1402 """ 1403 c = self.cardinality() > 1404 r = randint(0, c1) 1405 return self.unrank(r) 1406 /scratch/ghitza/sage5.0.beta10/local/lib/python2.7/sitepackages/sage/misc/prandom.pyc in randint(a, b) 114 46 115 """ > 116 return _pyrand().randint(a, b) 117 118 def choice(seq): /scratch/ghitza/sage5.0.beta10/local/lib/python/random.pyc in randint(self, a, b) 239 """ 240 > 241 return self.randrange(a, b+1) 242 243 def _randbelow(self, n, _log=_log, int=int, _maxwidth=1L<<BPF, /scratch/ghitza/sage5.0.beta10/local/lib/python/random.pyc in randrange(self, start, stop, step, int, default, maxwidth) 193 194 # stop argument supplied. > 195 istop = int(stop) 196 if istop != stop: 197 raise ValueError, "noninteger stop for randrange()" TypeError: int() argument must be a string or a number, not 'PlusInfinity'
Attachments (1)
Change History (29)
comment:1 Changed 9 years ago by
Milestone:  sage5.11 → sage5.12 

comment:2 Changed 9 years ago by
Status:  new → needs_review 

Changed 9 years ago by
Attachment:  trac_12867.patch added 

comment:3 Changed 9 years ago by
Well, what about raising an exception saying that there is no uniform distribution on this set ?...
Honestly, computing random words through __random_element_from_unrank
really is a joke....
sage: W=Words(2, 30) sage: W.random_element() <still waiting>
Nathann
comment:4 Changed 9 years ago by
Branch:  → u/ncohen/12867 

The new branch u/ncohen/12867 implements three random_element
for the different kinds of words that Sage supports. It also moves the ._iter_
methods where it belongs, for the set of "all words on 3 letters" is not countable and should not have an ._iter_
method (unless somebody wants to implement one for RR).
It also removes a deprecated function.
Nathann
comment:5 Changed 9 years ago by
Commit:  → df4cab0a9e03d2fadd3b714100ede7c52c3fb0ef 

comment:6 Changed 9 years ago by
Cc:  Sage Combinat CC user Vincent Delecroix Franco Saliola Sébastien Labbé added 

comment:7 Changed 9 years ago by
It would be better to use the new doc continuation ...:
instead of ...
comment:8 Changed 9 years ago by
I fixed this, as well as the broken doctests reported by the patchbot in sage/categories/modules_with_basis.py
and sage/algebras/shuffle_algebra.py
.
The first one has been fixed with Darij's help : turns out that Sage's example of a free algebra was not a free algebra (see [1]).
The second one has been fixed by building manually an element of a Shuffle Algebra instead of relying on an_element()
, which always returns 0.
Patch updated (and rebased)
Nathann
[1] https://groups.google.com/d/topic/sagecombinatdevel/zdN44XJZu5s/discussion
comment:9 Changed 9 years ago by
Commit:  df4cab0a9e03d2fadd3b714100ede7c52c3fb0ef → e9d71cc29cada6747f82d0a71c0653afe52c0d50 

comment:10 Changed 9 years ago by
Commit:  e9d71cc29cada6747f82d0a71c0653afe52c0d50 → 241a151def174f9cfa93340fd3dd2a9be1d4aa81 

comment:11 Changed 9 years ago by
Milestone:  sage6.1 → sage6.2 

comment:12 Changed 9 years ago by
Commit:  241a151def174f9cfa93340fd3dd2a9be1d4aa81 → eb7c2ab4e9cca0cb584f2236334db9dae4f41a75 

Branch pushed to git repo; I updated commit sha1. New commits:
eb7c2ab  Trac #12867: Rebase on 6.2.beta0

comment:14 Changed 9 years ago by
Commit:  eb7c2ab4e9cca0cb584f2236334db9dae4f41a75 → 035603dd0c523ff054ffdc2d993b1898d827cf3a 

Branch pushed to git repo; I updated commit sha1. New commits:
035603d  trac #12867: rebase on 6.2.beta5

comment:16 followup: 17 Changed 8 years ago by
Status:  needs_review → needs_work 

Hi there,
Suggestions, tasks and questions:
0) Might be rebased for 6.2.rc0
1) Add doctest for your errors
2) The following code
self((self.alphabet()[randint(0,n1)] for x in range(self._length)))
does not handle all cases. For example
sage: W = Words(GF(5), length=4) sage: W.random_element() KABOOM
The problem is that you really do not know what is the __getitem__
there. A possibility is
self((self.alphabet().random_element() for _ in range(self._length)))
3) What is the purpose of the commit 241a151def174f9cfa93340fd3dd2a9be1d4aa81 that modifies stuff in shuffle_algebra.py, algebras_with_basis.py, lyndon_word.py, etc?
Vincent
comment:17 Changed 8 years ago by
YO !
0) Might be rebased for 6.2.rc0
Done, but there was no conflict with 6.2.rc0....
1) Add doctest for your errors
Well, this is in the branch
+ sage: W = Words(5) + sage: W.random_element() # random
What else do you expect to find ?
2) The following code
self((self.alphabet()[randint(0,n1)] for x in range(self._length)))does not handle all cases. For example
sage: W = Words(GF(5), length=4) sage: W.random_element() KABOOMThe problem is that you really do not know what is the
__getitem__
there. A possibility isself((self.alphabet().random_element() for _ in range(self._length)))
Well, a list has no .random_element()
method. Would that work ?
Otherwise we could call list(self.alphabet())
. Or make sure self.alphabet() is a list. What do you think ?
3) What is the purpose of the commit 241a151def174f9cfa93340fd3dd2a9be1d4aa81 that modifies stuff in shuffle_algebra.py, algebras_with_basis.py, lyndon_word.py, etc?
HMmmmmm... Officially, it is to fix a bug because the current status is incorrect. I asked around and it turns out that these things are only defined on finite words. I don't even know what they are, but doctests were broken otherwise. So well. Everybody's happy this way :P
Nathann
comment:18 Changed 8 years ago by
Commit:  035603dd0c523ff054ffdc2d993b1898d827cf3a → 61f563aceb93a5c39febe59c0bff679ef8a29a52 

Branch pushed to git repo; I updated commit sha1. New commits:
61f563a  trac #16287: Merged into 6.2.rc0

comment:19 Changed 8 years ago by
Commit:  61f563aceb93a5c39febe59c0bff679ef8a29a52 → a4095e1f8b27a9429db19bf6698022eb971d1a36 

Branch pushed to git repo; I updated commit sha1. New commits:
a4095e1  trac #12867: Bugfix

comment:20 Changed 8 years ago by
Status:  needs_work → needs_review 

Well... Turns out that the lists were already wrapped with something that provides a random_element
method...
Nathann
comment:21 Changed 8 years ago by
Branch:  u/ncohen/12867 → public/12867 

Commit:  a4095e1f8b27a9429db19bf6698022eb971d1a36 → 3adf50879e44d290936f74acab9e62c12cf1b434 
You forgot to remove the "import randint" and did not test all errors... If you are happy with the public branch then set positive review.
New commits:
3adf508  remove unused import + doctest

comment:22 Changed 8 years ago by
Authors:  → Nathann Cohen 

Reviewers:  → Vincent Delecroix 
Status:  needs_review → positive_review 
Tests pass, and I am happy to see this fixed at last.
Nathann
comment:23 Changed 8 years ago by
Milestone:  sage6.2 → sage6.3 

comment:25 Changed 8 years ago by
Because of trac #8389... The fix is apparently trivial, checking that all tests pass right now ...
Nathann
comment:26 Changed 8 years ago by
Commit:  3adf50879e44d290936f74acab9e62c12cf1b434 → 3f13460e1441bfaf2d5539262add1ad056f9fb7d 

comment:27 Changed 8 years ago by
Status:  needs_work → positive_review 

comment:28 Changed 8 years ago by
Branch:  public/12867 → 3f13460e1441bfaf2d5539262add1ad056f9fb7d 

Resolution:  → fixed 
Status:  positive_review → closed 
Here is a proposal, needs review.