Opened 7 years ago

Closed 5 years ago

#12867 closed defect (fixed)

random_element for Words is broken

Reported by: AlexGhitza Owned by: sage-combinat
Priority: major Milestone: sage-6.3
Component: combinatorics Keywords:
Cc: sage-combinat, 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/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 chapoton 6 years ago.

Download all attachments as: .zip

Change History (29)

comment:1 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:2 Changed 6 years ago by chapoton

  • Status changed from new to needs_review

Here is a proposal, needs review.

Changed 6 years ago by chapoton

comment:3 Changed 6 years ago by ncohen

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 6 years ago by ncohen

  • 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 6 years ago by git

  • Commit set to 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 6 years ago by ncohen

  • Cc sage-combinat vdelecroix saliola slabbe added

comment:7 Changed 6 years ago by chapoton

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

comment:8 Changed 6 years ago by ncohen

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 6 years ago by ncohen

  • Commit changed from df4cab0a9e03d2fadd3b714100ede7c52c3fb0ef to e9d71cc29cada6747f82d0a71c0653afe52c0d50

(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 6 years ago by ncohen

  • Commit changed from e9d71cc29cada6747f82d0a71c0653afe52c0d50 to 241a151def174f9cfa93340fd3dd2a9be1d4aa81

Banch updated !

Nathann


New commits:

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

comment:11 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:12 Changed 5 years ago by git

  • Commit changed from 241a151def174f9cfa93340fd3dd2a9be1d4aa81 to eb7c2ab4e9cca0cb584f2236334db9dae4f41a75

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

eb7c2abTrac #12867: Rebase on 6.2.beta0

comment:13 Changed 5 years ago by ncohen

Rebased on 6.2.beta0 !

Nathann

comment:14 Changed 5 years ago by git

  • Commit changed from eb7c2ab4e9cca0cb584f2236334db9dae4f41a75 to 035603dd0c523ff054ffdc2d993b1898d827cf3a

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

035603dtrac #12867: rebase on 6.2.beta5

comment:15 Changed 5 years ago by ncohen

rebased again ....

comment:16 follow-up: Changed 5 years ago by vdelecroix

  • 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,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 5 years ago by ncohen

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 5 years ago by git

  • Commit changed from 035603dd0c523ff054ffdc2d993b1898d827cf3a to 61f563aceb93a5c39febe59c0bff679ef8a29a52

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

61f563atrac #16287: Merged into 6.2.rc0

comment:19 Changed 5 years ago by git

  • Commit changed from 61f563aceb93a5c39febe59c0bff679ef8a29a52 to a4095e1f8b27a9429db19bf6698022eb971d1a36

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

a4095e1trac #12867: Bugfix

comment:20 Changed 5 years ago by ncohen

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

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

3adf508remove unused import + doctest

comment:22 Changed 5 years ago by ncohen

  • Authors set to Nathann Cohen
  • 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 vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:24 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

Tests don't pass

comment:25 Changed 5 years ago by ncohen

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

Nathann

comment:26 Changed 5 years ago by git

  • Commit changed from 3adf50879e44d290936f74acab9e62c12cf1b434 to 3f13460e1441bfaf2d5539262add1ad056f9fb7d

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 5 years ago by ncohen

  • Status changed from needs_work to positive_review

comment:28 Changed 5 years ago by vbraun

  • Branch changed from public/12867 to 3f13460e1441bfaf2d5539262add1ad056f9fb7d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.