Thematic tutorial on combinatorics

[nthiery]

This ticket adds a thematic tutorial on combinatorics, translated from the combinatorics chapter of the book "Calcul Mathématique avec Sage" [1] by Hugh Thomas. Result compiled by sphinx available on [2]

[1]  http://sagebook.gforge.inria.fr/

[2]  http://combinat.sagemath.org/doc/reference/sage/combinat/tutorial.html

[nthiery]

Hi Hugh,

The conversion to ReST should be finished. The two remaining things that remain to do:

• A complete proofreading
• Adding a link from the main Thematic Tutorials index

[nthiery]

I forgot to mention that all tests pass.

[hthomas]

\dots in the source, not in math mode (eg. at line 113 of the tex source) turns into nothing in the tutorial.

Images don't seem to be working -- not Sage output figures, and not embedded figures (eg {fig:combinatoire:exemples:catalan:arbres}).

Maybe it would be nice to number the exercises, or at least indicate where a new one starts (other than by a blank line)?

The link to \ref{exo.enumeration.arbres} doesn't work (line 517 of the tex source).

Something bad happened in the conversion at line 757 in the tex source. (In the tutorial, search for "We can now calculate coefficients much further") Similar problem at line 846 of the source (search for "or, in a more readable format".

"This takes a couple seconds" doesn't appear in the tex source. It should be "a couple of seconds".

line 860: \QQ didn't convert properly (maybe because it's within a \emph?)

line 906: display didn't convert properly. (Search for "In this simple case".)

12. 999: the subsubsection title Synthese didn't convert properly. And now I notice that I didn't translate the title!

12. 1035: the link to a different chapter of the book doesn't work (surprise).

12. 1223 \Python disappears. Again on line 1622, 1649, 2029.

12. 1359: "A 3 dollar bill and a 5 dollar bill" would be better than "A 3 and a 5 dollar bir" (which is a mistake that got introduced when fixing up the conversion.

12. 1496: sage output graphic doesn't appear, similarly l. 1514

l, 1570: here, exercises are labelled "Exercise" but not earlier.

12. 2119: here, and elsewhere, it would be nice if the two consecutive sageexamples were displayed without a break between them.

12. 2286: \command{cartesian\_product} didn't convert well.

12. 2620 \latte disappears

12. 2624 \palp disappears

[hthomas]

The previous issues are fixed either by me, or by Nicolas, except:

\dots in the source, not in math mode (eg. at line 113 of the tex source) turns into nothing in the tutorial. Partial orders on a set of 8 elements, up to isomorphism -- there is a missing sage image output.

The link to \ref{exo.enumeration.arbres} doesn't work (line 517 of the tex source). Something bad happened in the conversion at line 757 in the tex source. (In the tutorial, search for "We can now calculate coefficients much further") Similar problem at line 846 of the source (search for "or, in a more readable format". line 860: \QQ didn't convert properly (maybe because it's within a \emph?)

line 906: display didn't convert properly. (Search for "In this simple case".)

12. 2119: here, and elsewhere, it would be nice if the two consecutive sageexamples were displayed without a break between them.

12. 2286: \command{cartesian\_product} didn't convert well.

[hthomas]

Everything is fixed except I think there are still two images missing.

Partial orders on a set of 8 elements, up to isomorphism (search for "partial orders on a set").

There is missing sage output .. image:: ../../media/combinat/graphs-5.png (search for "Here are those with at most")

[nthiery]

Good morning Hugh!

Replying to hthomas:

Everything is fixed except I think there are still two images missing.

Thanks!

Partial orders on a set of 8 elements, up to isomorphism (search for "partial orders on a set").

There is missing sage output .. image:: ../../media/combinat/graphs-5.png (search for "Here are those with at most")

I just pushed a reviewer patch on the queue doing that and a couple other minor improvements. If you are happy we my changes, I guess we can fold everything together, and declare it as done.

I am heading for the CRM now.

Cheers,

Nicolas

[nthiery]

Ok, we are just waiting for some proofreading notes a colleague here, and it's good to go!

[nthiery]

Thanks Timothy, your proofreading has been super useful!

After a last round of checking, here is the final patch, all good to go.

Hugh: it's been a pleasure collaborating with you on this one :-)

Cheers,

Nicolas

[jdemeyer]

There are a few doctest failures:

**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.1.beta1/devel/sage-main/sage/combinat/tutorial.py", line 664:
    sage: S.cardinality()                     # long time
Expected:
    2003529930406846464979072351560255750447825475569751419265016973
    ...736L
Got:
    20035299304068464649790[didn't copy]905719156736
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.1.beta1/devel/sage-main/sage/combinat/tutorial.py", line 675:
    sage: S.unrank(237102123)                 # long time
Expected:
    {{{2}, {3}, {1, 2, 3, 4}, {1, 2}, {1, 4}, {}, {2, 3, 4},
    {1, 2, 4}, {3, 4}, {4}, {2, 3}, {1, 2, 3}}, {{2}, {3},
    {1, 2, 3, 4}, {1, 2}, {1, 4}, {2, 3, 4}, {3, 4},
    {1, 3, 4}, {1}, {1, 3}, {1, 2, 3}}}
Got:
    {{{3}, {1, 2, 3, 4}, {1, 2}, {1, 4}, {}, {2, 3, 4}, {1, 2, 4}, {3, 4}, {4}, {2, 3}, {1, 2, 3}, {2}}, {{3}, {1, 2, 3, 4}, {1, 2}, {1, 4
}, {2, 3, 4}, {3, 4}, {1, 3, 4}, {1}, {1, 3}, {1, 2, 3}, {2}}}
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.1.beta1/devel/sage-main/sage/combinat/tutorial.py", line 1169:
    sage: sum( x^len(s) for s in Subsets(8) )
Expected:
    x^8 + 8*x^7 + 28*x^6 + 56*x^5 + 70*x^4 + 56*x^3 + 28*x^2 + 8*x + 1
Got:
    976273994417299685848067930754598608313151518561000000000000000000000000
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.1.beta1/devel/sage-main/sage/combinat/tutorial.py", line 1174:
    sage: sum( x^p.length() for p in Permutations(3) )
Expected:
    x^3 + 2*x^2 + 2*x + 1
Got:
    991035918113904045988003000
**********************************************************************
File "/padic/scratch/jdemeyer/merger/sage-5.1.beta1/devel/sage-main/sage/combinat/tutorial.py", line 1179:
    sage: factor(sum( x^p.length() for p in Permutations(3) ))
Expected:
    (x + 1)*(x^2 + x + 1)
Got:
    2^3 * 5^3 * 7^2 * 20347 * 80929 * 12282556080169
**********************************************************************

[nthiery]

Replying to jdemeyer:

There are a few doctest failures:

Ah shoot, sorry, long tests of course. Fixed in the attached patch.

Thanks,

Nicolas

[jhpalmieri]

I'm curious about why this is part of the reference manual, not the thematic tutorials.

[jdemeyer]

Replying to jhpalmieri:

I'm curious about why this is part of the reference manual, not the thematic tutorials.

Good point, this should be addressed.

[nthiery]

Replying to jdemeyer:

Replying to jhpalmieri:

I'm curious about why this is part of the reference manual, not the thematic tutorials.

We have discussed this quite some with the Sage-Combinat people. Here is the rationale for putting a thematic tutorial in the Sage sources when there is a natural spot for it ("transversal" tutorials should definitely go in the thematic tutorial directory):

• It's available from sage: sage.combinat.tutorial? which I find a very desirable feature.

• It keeps it close to the related sources. Among the advantages are:
  • a curious reader browsing the sources will find it
  • running sage -t on sage.combinat will run the tests there
  • grepping or query/replacing through sage/combinat will find it

• It's possible to refer to it from the reference manual (ok, that's a bad argument: linking the thematic tutorials from the reference manual ought to be possible, but this is another story).

Note that we already have a sage.rings.padics.tutorial.

Of course, this tutorial should be linked from the thematic tutorial index. The reason I did not do it right away is that there is a patch with other tutorials coming shortly which includes a bit of reorganization of the that index, and I wanted to avoid trivial conflicts.

What do you think?

I am putting this back to needs review, and let you put it back to positive review.

Cheers,

Nicolas

[jhpalmieri]

Replying to nthiery:

Replying to jdemeyer:

Replying to jhpalmieri:

I'm curious about why this is part of the reference manual, not the thematic tutorials.

• It's available from sage: sage.combinat.tutorial? which I find a very desirable feature.

If it were in thematic tutorials, something like this still ought to be doable (say, using sage.combinat.tutorial() instead), using modifications of the commands from sagedoc.py that allow tutorial() to open the tutorial.

Anyway, my original question was, as I said, a matter of curiosity, not a criticism. I don't mind setting this back to "positive review", although it would be good (on another ticket – please cc me if you open one) to tidy up the documentation in the ways you seem to suggest in your comment. And the code in sagedoc.py could be modified to allow easy opening of the various thematic tutorials.

Jeroen: any objections?

[nthiery]

Hi John,

Replying to jhpalmieri:

If it were in thematic tutorials, something like this still ought to be doable (say, using sage.combinat.tutorial() instead), using modifications of the commands from sagedoc.py that allow tutorial() to open the tutorial.

Yeah, but it's really not as good: you need to teach people yet another way to access documentation. The user should just need to know about '?'.

Anyway, my original question was, as I said, a matter of curiosity, not a criticism.

I definitely was a good question. And I wanted to take the time to answer since others are likely to ask it as well :-)

I don't mind setting this back to "positive review", although it would be good (on another ticket – please cc me if you open one) to tidy up the documentation in the ways you seem to suggest in your comment.

Thanks for your interest. I hope to get to this done soon: we want this to be in Sage for the Sage Days in July! Now, I'll be traveling around the next couple weeks, so don't hold too much your breath.

Cheers,

Nicolas

[nthiery]

Replying to jhpalmieri:

Jeroen: any objections?

I assume no objections. Back to positive review!

[nthiery]

Yippee!

Thanks everyone!

[jdemeyer]

This takes a really long time to --long doctest (180 seconds on sage.math).

Can you either simplify some doctests or split up this file?

[nthiery]

Replying to jdemeyer:

This takes a really long time to --long doctest (180 seconds on sage.math).

Can you either simplify some doctests or split up this file?

In the upcoming updated patch, I have fixed the tutorial to not test at all one of the longest tests (it was marked random anyway), and to avoid a recomputation in another long test. I used the occasion to record the time needed for the other long tests. On my machine running the tests with -long goes from 65s down to 35s. I guess that should do the job.

Jeroen: since the change is essentially trivial and is only about doctests (see diff below), do you mind reviewing it, just to make the merge cycle faster?

Thanks!

Nicolas

sage/combinat/tutorial.py

@@ -661 +661 @@
 
     sage: E = Set([1,2,3,4])
     sage: S = Subsets(Subsets(Subsets(E)))
-    sage: S.cardinality()                     # long time
+    sage: n = S.cardinality(); n              # long time (10s, 2012)
     2003529930406846464979072351560255750447825475569751419265016973...
 
 which is roughly `2\cdot 10^{19728}`::
 
-    sage: S.cardinality().ndigits()           # long time
+    sage: n.ndigits()                         # long time
     19729
 
 or ask for its `237102124`-th element::
 
-    sage: S.unrank(237102123)                 # long time # random
+    sage: S.unrank(237102123)                 # not tested (20s, 2012)
     {{{2}, {3}, {1, 2, 3, 4}, {1, 2}, {1, 4}, {}, {2, 3, 4},
     {1, 2, 4}, {3, 4}, {4}, {2, 3}, {1, 2, 3}}, {{2}, {3},
     {1, 2, 3, 4}, {1, 2}, {1, 4}, {2, 3, 4}, {3, 4},
@@ -1143 +1143 @@
     ::
 
         sage: cubes = [t**3 for t in range(-999,1000)]
-        sage: exists([(x,y) for x in cubes for y in cubes],  # long time
+        sage: exists([(x,y) for x in cubes for y in cubes],  # long time (3s, 2012)
         ...          lambda (x,y): x+y == 218)
         (True, (-125, 343))
-        sage: exists(((x,y) for x in cubes for y in cubes),  # long time
+        sage: exists(((x,y) for x in cubes for y in cubes),  # long time (2s, 2012)
         ...          lambda (x,y): x+y == 218)
         (True, (-125, 343))
 

[nthiery]

Jeroen: since the change is essentially trivial and is only about doctests (see diff below), do you mind reviewing it, just to make the merge cycle faster?

Hugh: feel free to beat Jeroen :-)

I really would like to see this in 5.1, for the upcoming Sage Days 40.

Cheers,

Nicolas

[hthomas]

For my laptop, it goes from 169 s to 102 s. I have set it back to positive review, subject to Jeroen's opinion about whether this speedup is sufficient.

cheers,

Hugh

[jdemeyer]

Sorry, sage-5.1 is done.

[jdemeyer]

At  http://trac.sagemath.org/sage_trac/ticket/6538#comment:8, there is a claim that a test added by this ticket is incorrect.

[nthiery]

Thanks Jeroen!