Opened 9 years ago

Closed 9 years ago

#12925 closed enhancement (fixed)

Thematic tutorial on combinatorics

Reported by: nthiery Owned by: sage-combinat
Priority: major Milestone: sage-5.2
Component: combinatorics Keywords: thematic tutorial
Cc: sage-combinat, hthomas Merged in: sage-5.2.rc0
Authors: Nicolas M. Thiéry, Hugh Thomas Reviewers: Hugh Thomas, Nicolas M. Thiéry, Timothy Walsh
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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]

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

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

Attachments (1)

trac_12925-combinatorics_thematic_tutorial-nt.patch (420.3 KB) - added by nthiery 9 years ago.

Download all attachments as: .zip

Change History (39)

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

comment:24 Changed 9 years ago by nthiery

Yippee!

Thanks everyone!

comment:25 follow-up: 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: 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 b calculate its cardinality (`2^{2^{2^4}}` 
    661661
    662662    sage: E = Set([1,2,3,4])
    663663    sage: S = Subsets(Subsets(Subsets(E)))
    664     sage: S.cardinality()                     # long time
     664    sage: n = S.cardinality(); n              # long time (10s, 2012)
    665665    2003529930406846464979072351560255750447825475569751419265016973...
    666666
    667667which is roughly `2\cdot 10^{19728}`::
    668668
    669     sage: S.cardinality().ndigits()           # long time
     669    sage: n.ndigits()                         # long time
    670670    19729
    671671
    672672or ask for its `237102124`-th element::
    673673
    674     sage: S.unrank(237102123)                 # long time # random
     674    sage: S.unrank(237102123)                 # not tested (20s, 2012)
    675675    {{{2}, {3}, {1, 2, 3, 4}, {1, 2}, {1, 4}, {}, {2, 3, 4},
    676676    {1, 2, 4}, {3, 4}, {4}, {2, 3}, {1, 2, 3}}, {{2}, {3},
    677677    {1, 2, 3, 4}, {1, 2}, {1, 4}, {2, 3, 4}, {3, 4},
    Alternatively, we could construct an int 
    11431143    ::
    11441144
    11451145        sage: cubes = [t**3 for t in range(-999,1000)]
    1146         sage: exists([(x,y) for x in cubes for y in cubes],  # long time
     1146        sage: exists([(x,y) for x in cubes for y in cubes],  # long time (3s, 2012)
    11471147        ...          lambda (x,y): x+y == 218)
    11481148        (True, (-125, 343))
    1149         sage: exists(((x,y) for x in cubes for y in cubes),  # long time
     1149        sage: exists(((x,y) for x in cubes for y in cubes),  # long time (2s, 2012)
    11501150        ...          lambda (x,y): x+y == 218)
    11511151        (True, (-125, 343))
    11521152

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: Changed 9 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:37 in reply to: ↑ 36 Changed 9 years ago by nthiery

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.