Opened 9 years ago

Closed 9 years ago

# Thematic tutorial on combinatorics

Reported by: Owned by: nthiery sage-combinat major sage-5.2 combinatorics thematic tutorial sage-combinat, hthomas sage-5.2.rc0 Nicolas M. Thiéry, Hugh Thomas Hugh Thomas, Nicolas M. Thiéry, Timothy Walsh N/A

### Description (last modified by 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]

### comment:1 Changed 9 years ago by leif

• Description modified (diff)

### comment:2 Changed 9 years ago by nthiery

• Cc hthomas added
• Status changed from new to needs_review

### comment:3 Changed 9 years ago by nthiery

• Reviewers set to Hugh Thomas, Nicolas M. Thiéry

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

### comment:4 Changed 9 years ago by nthiery

I forgot to mention that all tests pass.

### comment:5 Changed 9 years ago by nthiery

• Description modified (diff)

### comment:6 Changed 9 years ago by nthiery

• Description modified (diff)

### comment:7 follow-up: ↓ 8 Changed 9 years ago by 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".)

1. 999: the subsubsection title Synthese didn't convert properly. And now I notice that I didn't translate the title!
1. 1035: the link to a different chapter of the book doesn't work (surprise).
1. 1223 \Python disappears. Again on line 1622, 1649, 2029.
1. 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.
1. 1496: sage output graphic doesn't appear, similarly l. 1514

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

1. 2119: here, and elsewhere, it would be nice if the two consecutive sageexamples were displayed without a break between them.
1. 2286: \command{cartesian\_product} didn't convert well.
1. 2620 \latte disappears
1. 2624 \palp disappears

### comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 9 years ago by 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".)

1. 2119: here, and elsewhere, it would be nice if the two consecutive sageexamples were displayed without a break between them.
1. 2286: \command{cartesian\_product} didn't convert well.

### comment:9 in reply to: ↑ 8 ; follow-up: ↓ 10 Changed 9 years ago by 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")

### comment:10 in reply to: ↑ 9 Changed 9 years ago by 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

### comment:11 Changed 9 years ago by nthiery

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

### comment:12 Changed 9 years ago by hthomas

• Reviewers changed from Hugh Thomas, Nicolas M. Thiéry to Hugh Thomas, Nicolas M. Thiéry, Timothy Walsh

### comment:13 Changed 9 years ago by nthiery

• Status changed from needs_review to positive_review

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

### comment:14 follow-up: ↓ 15 Changed 9 years ago by jdemeyer

• Status changed from positive_review to needs_work

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
**********************************************************************


### comment:15 in reply to: ↑ 14 Changed 9 years ago by nthiery

• Status changed from needs_work to positive_review

Replying to jdemeyer:

There are a few doctest failures:

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

Thanks,

Nicolas

### comment:16 follow-up: ↓ 17 Changed 9 years ago by jhpalmieri

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

### comment:17 in reply to: ↑ 16 ; follow-up: ↓ 18 Changed 9 years ago by jdemeyer

• Status changed from positive_review to needs_work
• Work issues set to move to devel/sage/doc

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.

### comment:18 in reply to: ↑ 17 ; follow-up: ↓ 19 Changed 9 years ago by nthiery

• Status changed from needs_work to needs_review

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

### comment:19 in reply to: ↑ 18 ; follow-ups: ↓ 20 ↓ 21 Changed 9 years ago by 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?

### comment:20 in reply to: ↑ 19 Changed 9 years ago by 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

### comment:21 in reply to: ↑ 19 Changed 9 years ago by nthiery

• Status changed from needs_review to positive_review

Replying to jhpalmieri:

Jeroen: any objections?

I assume no objections. Back to positive review!

### comment:22 Changed 9 years ago by jdemeyer

• Work issues move to devel/sage/doc deleted

### comment:23 Changed 9 years ago by jdemeyer

• Merged in set to sage-5.1.beta4
• Resolution set to fixed
• Status changed from positive_review to closed

Yippee!

Thanks everyone!

### comment:25 follow-up: ↓ 28 Changed 9 years ago by jdemeyer

• Merged in sage-5.1.beta4 deleted
• Resolution fixed deleted
• Status changed from closed to new

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?

### comment:26 Changed 9 years ago by jdemeyer

• Status changed from new to needs_review

### comment:27 Changed 9 years ago by jdemeyer

• Status changed from needs_review to needs_work

### comment:28 in reply to: ↑ 25 ; follow-up: ↓ 29 Changed 9 years ago by 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

diff --git a/sage/combinat/tutorial.py b/sage/combinat/tutorial.py
 a 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}, 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))

### comment:29 in reply to: ↑ 28 Changed 9 years ago by 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

### comment:30 Changed 9 years ago by nthiery

• Status changed from needs_work to needs_review

### comment:31 Changed 9 years ago by hthomas

• Status changed from needs_review to positive_review

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

### comment:32 Changed 9 years ago by jdemeyer

• Milestone changed from sage-5.1 to sage-5.2

Sorry, sage-5.1 is done.

### comment:33 Changed 9 years ago by jdemeyer

• Merged in set to sage-5.2.beta1
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:34 Changed 9 years ago by jdemeyer

• Merged in sage-5.2.beta1 deleted
• Resolution fixed deleted
• Status changed from closed to new

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

### comment:35 Changed 9 years ago by jdemeyer

• Status changed from new to needs_review

### comment:36 follow-up: ↓ 37 Changed 9 years ago by jdemeyer

• Status changed from needs_review to positive_review

Thanks Jeroen!

### comment:38 Changed 9 years ago by jdemeyer

• Merged in set to sage-5.2.rc0
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.