Opened 7 years ago
Closed 5 years ago
#12867 closed defect (fixed)
random_element for Words is broken
Reported by:  AlexGhitza  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage6.3 
Component:  combinatorics  Keywords:  
Cc:  sagecombinat, vdelecroix, saliola, slabbe  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  3f13460 (Commits)  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 5 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:2 Changed 5 years ago by
 Status changed from new to needs_review
Changed 5 years ago by
comment:3 Changed 5 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 5 years ago by
 Branch set to 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 5 years ago by
 Commit set to df4cab0a9e03d2fadd3b714100ede7c52c3fb0ef
comment:6 Changed 5 years ago by
 Cc sagecombinat vdelecroix saliola slabbe added
comment:7 Changed 5 years ago by
It would be better to use the new doc continuation ...:
instead of ...
comment:8 Changed 5 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 5 years ago by
 Commit changed from df4cab0a9e03d2fadd3b714100ede7c52c3fb0ef to e9d71cc29cada6747f82d0a71c0653afe52c0d50
comment:10 Changed 5 years ago by
 Commit changed from e9d71cc29cada6747f82d0a71c0653afe52c0d50 to 241a151def174f9cfa93340fd3dd2a9be1d4aa81
comment:11 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:12 Changed 5 years ago by
 Commit changed from 241a151def174f9cfa93340fd3dd2a9be1d4aa81 to eb7c2ab4e9cca0cb584f2236334db9dae4f41a75
Branch pushed to git repo; I updated commit sha1. New commits:
eb7c2ab  Trac #12867: Rebase on 6.2.beta0

comment:13 Changed 5 years ago by
Rebased on 6.2.beta0 !
Nathann
comment:14 Changed 5 years ago by
 Commit changed from eb7c2ab4e9cca0cb584f2236334db9dae4f41a75 to 035603dd0c523ff054ffdc2d993b1898d827cf3a
Branch pushed to git repo; I updated commit sha1. New commits:
035603d  trac #12867: rebase on 6.2.beta5

comment:15 Changed 5 years ago by
rebased again ....
comment:16 followup: ↓ 17 Changed 5 years ago by
 Status changed from needs_review to 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 in reply to: ↑ 16 Changed 5 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 5 years ago by
 Commit changed from 035603dd0c523ff054ffdc2d993b1898d827cf3a to 61f563aceb93a5c39febe59c0bff679ef8a29a52
Branch pushed to git repo; I updated commit sha1. New commits:
61f563a  trac #16287: Merged into 6.2.rc0

comment:19 Changed 5 years ago by
 Commit changed from 61f563aceb93a5c39febe59c0bff679ef8a29a52 to a4095e1f8b27a9429db19bf6698022eb971d1a36
Branch pushed to git repo; I updated commit sha1. New commits:
a4095e1  trac #12867: Bugfix

comment:20 Changed 5 years ago by
 Status changed from needs_work to needs_review
Well... Turns out that the lists were already wrapped with something that provides a random_element
method...
Nathann
comment:21 Changed 5 years ago by
 Branch changed from u/ncohen/12867 to public/12867
 Commit changed from a4095e1f8b27a9429db19bf6698022eb971d1a36 to 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 5 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
Tests pass, and I am happy to see this fixed at last.
Nathann
comment:23 Changed 5 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:24 Changed 5 years ago by
 Status changed from positive_review to needs_work
Tests don't pass
comment:25 Changed 5 years ago by
Because of trac #8389... The fix is apparently trivial, checking that all tests pass right now ...
Nathann
comment:26 Changed 5 years ago by
 Commit changed from 3adf50879e44d290936f74acab9e62c12cf1b434 to 3f13460e1441bfaf2d5539262add1ad056f9fb7d
comment:27 Changed 5 years ago by
 Status changed from needs_work to positive_review
comment:28 Changed 5 years ago by
 Branch changed from public/12867 to 3f13460e1441bfaf2d5539262add1ad056f9fb7d
 Resolution set to fixed
 Status changed from positive_review to closed
Here is a proposal, needs review.