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: sage-6.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:

Status badges

Description

sage: W = Words(5)
sage: W.random_element()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/ghitza/<ipython console> in <module>()

/scratch/ghitza/sage-5.0.beta10/local/lib/python2.7/site-packages/sage/combinat/combinat.pyc in __random_element_from_unrank(self)
   1402         """
   1403         c = self.cardinality()
-> 1404         r = randint(0, c-1)
   1405         return self.unrank(r)
   1406 

/scratch/ghitza/sage-5.0.beta10/local/lib/python2.7/site-packages/sage/misc/prandom.pyc in randint(a, b)
    114         -46
    115     """
--> 116     return _pyrand().randint(a, b)
    117 
    118 def choice(seq):

/scratch/ghitza/sage-5.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/sage-5.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, "non-integer stop for randrange()"

TypeError: int() argument must be a string or a number, not 'PlusInfinity'

Attachments (1)

trac_12867.patch (1.2 KB) - added by Frédéric Chapoton 9 years ago.

Download all attachments as: .zip

Change History (29)

comment:1 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11sage-5.12

comment:2 Changed 9 years ago by Frédéric Chapoton

Status: newneeds_review

Here is a proposal, needs review.

Changed 9 years ago by Frédéric Chapoton

Attachment: trac_12867.patch added

comment:3 Changed 9 years ago by Nathann Cohen

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

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 git

Commit: df4cab0a9e03d2fadd3b714100ede7c52c3fb0ef

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

df4cab0trac #12867: Implements random_element methods for Words and moves ._iter_

comment:6 Changed 9 years ago by Nathann Cohen

Cc: Sage Combinat CC user Vincent Delecroix Franco Saliola Sébastien Labbé added

comment:7 Changed 9 years ago by Frédéric Chapoton

It would be better to use the new doc continuation ...: instead of ...

comment:8 Changed 9 years ago by Nathann Cohen

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/sage-combinat-devel/zdN44XJZu5s/discussion

comment:9 Changed 9 years ago by Nathann Cohen

Commit: df4cab0a9e03d2fadd3b714100ede7c52c3fb0efe9d71cc29cada6747f82d0a71c0653afe52c0d50

(even though there is no automatic git message)


New commits:

e9d71cctrac #12867: Doctests fixed and ... changed to ....:
0380d55trac #12867: Rebase on 6.1.beta3

comment:10 Changed 9 years ago by Nathann Cohen

Commit: e9d71cc29cada6747f82d0a71c0653afe52c0d50241a151def174f9cfa93340fd3dd2a9be1d4aa81

Banch updated !

Nathann


New commits:

241a151trac #12867: Doctests fixed and ... changed to ....:
06d63d4trac #12867: Rebase on 6.1.beta4

comment:11 Changed 9 years ago by For batch modifications

Milestone: sage-6.1sage-6.2

comment:12 Changed 9 years ago by git

Commit: 241a151def174f9cfa93340fd3dd2a9be1d4aa81eb7c2ab4e9cca0cb584f2236334db9dae4f41a75

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

eb7c2abTrac #12867: Rebase on 6.2.beta0

comment:13 Changed 9 years ago by Nathann Cohen

Rebased on 6.2.beta0 !

Nathann

comment:14 Changed 9 years ago by git

Commit: eb7c2ab4e9cca0cb584f2236334db9dae4f41a75035603dd0c523ff054ffdc2d993b1898d827cf3a

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

035603dtrac #12867: rebase on 6.2.beta5

comment:15 Changed 9 years ago by Nathann Cohen

rebased again ....

comment:16 Changed 8 years ago by Vincent Delecroix

Status: needs_reviewneeds_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,n-1)] 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 8 years ago by Nathann Cohen

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,n-1)] 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)))

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 git

Commit: 035603dd0c523ff054ffdc2d993b1898d827cf3a61f563aceb93a5c39febe59c0bff679ef8a29a52

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

61f563atrac #16287: Merged into 6.2.rc0

comment:19 Changed 8 years ago by git

Commit: 61f563aceb93a5c39febe59c0bff679ef8a29a52a4095e1f8b27a9429db19bf6698022eb971d1a36

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

a4095e1trac #12867: Bugfix

comment:20 Changed 8 years ago by Nathann Cohen

Status: needs_workneeds_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 Vincent Delecroix

Branch: u/ncohen/12867public/12867
Commit: a4095e1f8b27a9429db19bf6698022eb971d1a363adf50879e44d290936f74acab9e62c12cf1b434

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:

3adf508remove unused import + doctest

comment:22 Changed 8 years ago by Nathann Cohen

Authors: Nathann Cohen
Reviewers: Vincent Delecroix
Status: needs_reviewpositive_review

Tests pass, and I am happy to see this fixed at last.

Nathann

comment:23 Changed 8 years ago by For batch modifications

Milestone: sage-6.2sage-6.3

comment:24 Changed 8 years ago by Volker Braun

Status: positive_reviewneeds_work

Tests don't pass

comment:25 Changed 8 years ago by Nathann Cohen

Because of trac #8389... The fix is apparently trivial, checking that all tests pass right now ...

Nathann

comment:26 Changed 8 years ago by git

Commit: 3adf50879e44d290936f74acab9e62c12cf1b4343f13460e1441bfaf2d5539262add1ad056f9fb7d

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

5899a33Merge branch 'public/12867' of trac.sagemath.org:sage into tmp
3f13460trac #12867: Broken doctests

comment:27 Changed 8 years ago by Nathann Cohen

Status: needs_workpositive_review

comment:28 Changed 8 years ago by Volker Braun

Branch: public/128673f13460e1441bfaf2d5539262add1ad056f9fb7d
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.