random_element for Words is broken

[Alex Ghitza]

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'

[Frédéric Chapoton]

Here is a proposal, needs review.

[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

[Nathann Cohen]

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

[git]

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

​df4cab0

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

[Frédéric Chapoton]

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

[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

[Nathann Cohen]

(even though there is no automatic git message)

---

New commits:

​e9d71cc	trac #12867: Doctests fixed and ... changed to ....:
​0380d55	trac #12867: Rebase on 6.1.beta3

[Nathann Cohen]

Banch updated !

Nathann

---

New commits:

​241a151	trac #12867: Doctests fixed and ... changed to ....:
​06d63d4	trac #12867: Rebase on 6.1.beta4

[git]

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

​eb7c2ab

Trac #12867: Rebase on 6.2.beta0

[Nathann Cohen]

Rebased on 6.2.beta0 !

Nathann

[git]

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

​035603d

trac #12867: rebase on 6.2.beta5

[Nathann Cohen]

rebased again ....

[Vincent Delecroix]

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

[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

[git]

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

​61f563a

trac #16287: Merged into 6.2.rc0

[git]

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

​a4095e1

trac #12867: Bugfix

[Nathann Cohen]

Well... Turns out that the lists were already wrapped with something that provides a random_element method...

Nathann

[Vincent Delecroix]

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

[Nathann Cohen]

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

Nathann

[Volker Braun]

Tests don't pass

[Nathann Cohen]

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

Nathann

[git]

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

​5899a33	Merge branch 'public/12867' of trac.sagemath.org:sage into tmp
​3f13460	trac #12867: Broken doctests