Stuffle algebra

[9e5e9644-03aa-4417-b4fb-5e7606a3aef2]

The stuffle (or quasi shuffle) algebra with counit and coproduct.

Apply:

• attachment: stuffle.patch​
• attachment: trac_14914_stuffle_addon1_fc.patch

Component: combinatorics

Keywords: stuffle quasi shuffle

Author: Matthieu Deneufchâtel

Branch/Commit: public/ticket/14914 @ 30cceb2

Issue created by migration from https://trac.sagemath.org/ticket/14914

[fchapoton]

Description changed:

--- 
+++ 
@@ -1 +1,6 @@
 The stuffle (or quasi shuffle) algebra with counit and coproduct.
+
+Apply:
+
+- [attachment: stuffle.patch​](https://github.com/sagemath/sage/files/ticket14914/c005c0f42c1c4c59c045cfa033cb13c8.gz)
+- [attachment: trac_14914_stuffle_addon1_fc.patch](https://github.com/sagemath/sage-prod/files/10658180/trac_14914_stuffle_addon1_fc.patch.gz)

[fchapoton]

comment:1

Attachment: stuffle.patch.gz

here is a first review patch, cleaning up and making sure that all tests pass

(check using sage -bt stuffle_algebra.py)

some somments:

TAB characters are forbidden in python, you should use 4 spaces. More generally one should avoid whitespaces at the end of the lines (trailing whitespaces) (check your text editor configuration)

the examples section should look like that:

EXAMPLES::

    sage: 2+2
    4

namely, with a shift of 4 spaces

If you want to work further on this ticket now, you should rather use a third patch on top of the two existing ones.

[tscrim]

comment:2

Hey Matthieu,

Is this patch ready for review (i.e. does it do everything you want it to)?

Best,

Travis

[fchapoton]

Attachment: trac_14914_stuffle_addon1_fc.patch.gz

[fchapoton]

Commit: 30cceb2

[fchapoton]

Branch: public/ticket/14914

[fchapoton]

Changed keywords from none to stuffle quasi shuffle

[fchapoton]

comment:4

turned into a git branch

---

New commits:

738c9fe	trac 14914 patch for stuffle algebras
30cceb2	trac #14914 clean up and lazy import into global namespace

[videlec]

Attachment: indexed_alphabet.py.gz

[videlec]

comment:5

The latex command \stuffle is not interpreted in the reference manual.

The (see above) is not appropriate. In this case it makes reference to another function. And indeed, in the reference manual, the class appears first. You can use the syntax :func:`the_name_of_my_function` to refer to a function. But in that case I would actually move the definition from the function to the class (since the entry point for the users is the class).

The first line of stuffle is W = Words(indexed_letters(40, names)). Why the hardcoded 40? Whatever number you put it will fail for some input! What you actually want to do is to work over the infinite alphabet a1, a2, .... You can find a draft of the kind of set you want in the attached file indexed_alphabet.py. With it you have

sage: A = IndexedAlphabet('a', 0, Infinity)
sage: A
Indexed alphabet {a0, a1, a2...}
sage: A[19]
'a19'
sage: A.cardinality()
+Infinity
sage: W = Words(A)
sage: W(['a0','a1','a19'])
word: a0,a1,a19

Once the above integrated, there is no need for an argument names in the function stuffle.

To test emptyness of a word you can do faster

sage: w = Word()
sage: if not w: print "I am empty"
I am empty