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

CC: @sagetrac-sage-combinat @hughrthomas

Component: combinatorics

Keywords: thematic tutorial

Author: Nicolas M. Thiéry, Hugh Thomas

Reviewer: Hugh Thomas, Nicolas M. Thiéry, Timothy Walsh

Merged: sage-5.2.rc0

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

[nthiery]

comment:3

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]

Reviewer: Hugh Thomas, Nicolas M. Thiéry

[nthiery]

comment:4

I forgot to mention that all tests pass.

[hughrthomas]

comment:7

\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".)

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

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

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

l. 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.

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

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

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

l. 2286: \command{cartesian_product} didn't convert well.

l. 2620 \latte disappears

l. 2624 \palp disappears

[hughrthomas]

comment:8

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".)

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

l. 2286: \command{cartesian_product} didn't convert well.

[hughrthomas]

comment:9

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]

comment:10

Good morning Hugh!

Replying to @hughrthomas:

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]

comment:11

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

[hughrthomas]

Changed reviewer from Hugh Thomas, Nicolas M. Thiéry to Hugh Thomas, Nicolas M. Thiéry, Timothy Walsh

[nthiery]

comment:13

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]

comment:14

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]

comment:15

Replying to @jdemeyer:

There are a few doctest failures:

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

Thanks,
Nicolas

[jhpalmieri]

comment:16

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

[jdemeyer]

comment:17

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.

[jdemeyer]

Work Issues: move to devel/sage/doc

[jdemeyer]

Changed merged from sage-5.1.beta4 to none

[nthiery]

comment:28

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

diff --git a/sage/combinat/tutorial.py b/sage/combinat/tutorial.py
--- a/sage/combinat/tutorial.py
+++ b/sage/combinat/tutorial.py
@@ -661,17 +661,17 @@ calculate its cardinality (`2^{2^{2^4}}`
 
     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,10 +1143,10 @@ Alternatively, we could construct an int
     ::
 
         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]

Attachment: trac_12925-combinatorics_thematic_tutorial-nt.patch.gz

[nthiery]

comment:29

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

[hughrthomas]

comment:31

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]

comment:32

Sorry, sage-5.1 is done.

[jdemeyer]

Merged: sage-5.2.beta1

[jdemeyer]

Changed merged from sage-5.2.beta1 to none

[jdemeyer]

comment:34

At [#6538 comment:8], there is a claim that a test added by this ticket is incorrect.

[nthiery]

comment:37

Thanks Jeroen!

[jdemeyer]

Merged: sage-5.2.rc0