Opened 6 years ago

Closed 6 years ago

#14562 closed enhancement (fixed)

Steiner Quadruple Systems

Reported by: ncohen Owned by: sage-combinat
Priority: major Milestone: sage-5.10
Component: combinatorics Keywords:
Cc: azi Merged in: sage-5.10.beta3
Authors: Nathann Cohen Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

Wow.

This patch is scary.

Really scary.

The construction is awful, and there's not much that I could do to make the code clear.

The point is that I do not understand the construction myself, and I did not try either, I just wanted to implement it. And it already took Quiiiiiiiiiiiiiite a lot of time, and headaches :-)

This patch implements a method that returns a Steiner Quadruple System whenever it exists. It follows the construction from Haim Hanani in a paper from 1960, which gives 6 differents constructions to make a large system from a small one, and all must be used to solve all cases.

Considering that I was able to test this code until n =300, and that all constructions have been tested for different values of n, I believe that this code is a correct counterpart of the paper itself. That's what makes me think that there is no typo in the code anymore (I fixed one thousand of them while writing it). So, even if it is very, very scary and unclear, I think that it is correct... Experimentally :-)

Nathann

Attachments (1)

trac_14562.patch (72.1 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 6 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 follow-up: Changed 6 years ago by rbeezer

Should one listen to "Le Blues Du Pauvre Delahaye" to properly review this? ;-)

comment:3 in reply to: ↑ 2 Changed 6 years ago by ncohen

Should one listen to "Le Blues Du Pauvre Delahaye" to properly review this? ;-)

Of course ! You would miss most of it otherwise. Here it is : http://www.steinertriples.fr/05%20Le%20Blues%20Du%20Pauvre%20Delahaye.m4a

Nathann

comment:4 follow-up: Changed 6 years ago by tmonteil

Hi Nathann,

concerning typos, i think that the new doctest trick

....: 

was created to correctly align the indentations. Hence, it could be better to add 4 spaces in your examples, instead of 3.

Meuuuuuuuuuh non t'es pas tout seul a chialer dans ta chambre.

comment:5 follow-up: Changed 6 years ago by tmonteil

From sage-devel mailing-list:

On Tuesday, March 19, 2013 12:51:32 PM UTC-4, Nathann Cohen wrote:
    Hellooooooooo !
    I personally totally hate cached functions. I hate them because I'm big enough to know what I should store and what I should not. 
    [...]

Ahem...

comment:6 follow-up: Changed 6 years ago by tmonteil

Will buying steinerquadruples.fr domain name be the opportunity for a good trade ?

comment:7 in reply to: ↑ 4 Changed 6 years ago by ncohen

was created to correctly align the indentations. Hence, it could be better to add 4 spaces in

Oh ? Well, I added four. But I don't get why : I think that the purpose was to align the length of this with the length of "sage:". So I thought that the number of spaces put use in front of an "if" is irrelevant O_o

Meuuuuuuuuuh non t'es pas tout seul a chialer dans ta chambre.

D'aileurs j'ai pas de chambre. Et en plus je suis pas seul parce que dans ma coloc y'avait un annif hier soir, et qu'il y avait tranquille 10 personnes qui campaient cte nuit. Dont deux dans ma chambre. Des gens bien :-D

Nathann

comment:8 in reply to: ↑ 5 Changed 6 years ago by ncohen

On Tuesday, March 19, 2013 12:51:32 PM UTC-4, Nathann Cohen wrote:
    Hellooooooooo !
    I personally totally hate cached functions. I hate them because I'm big enough to know what I should store and what I should not. 
    [...]

Ahem...

Ahahahah. Yeah, right. And in that case I wanted to store them :-D

The point is that while I was writing this patch I had a loop trying to build all SQS from 4 to 100, and it was slightly faster when cached. If you think that it is useless here I will remove it. I don't mind much :-)

Nathann

comment:9 in reply to: ↑ 6 Changed 6 years ago by ncohen

Will buying steinerquadruples.fr domain name be the opportunity for a good trade ?

I honestly thought of buying it while I was writing this patch :-PPPPP

Nathann

comment:10 follow-up: Changed 6 years ago by azi

Hello!

Don't ask how I came to this ticket.

I have a question. Is there a reason you use

{{{ for i in range(n) }}}

instead of

for i in xrange(n)

?

Best,

J

comment:11 Changed 6 years ago by azi

  • Cc azi added

Changed 6 years ago by ncohen

comment:12 in reply to: ↑ 10 Changed 6 years ago by ncohen

Helloooooo !

Don't ask how I came to this ticket.

Come on... Now I *have* to ask :-PPP

I have a question. Is there a reason you use

{{{ for i in range(n) }}}

instead of

for i in xrange(n)

None. Fixed :-)

Nathann

comment:13 Changed 6 years ago by nthiery

Well, at this rate, there would be zillion of places to update in the Sage source tree. And this issue will disapear when we switch ... some day ... to Python 3.0. So I would not worry too much about range vs xrange unless we know that n is likely to be huge.

comment:14 follow-up: Changed 6 years ago by vbraun

If speed is really an issue then you should switch to Cython, which will expand for i in range() directly into the corresponding C loop. So there isn't that much need for xrange() in Sage.

Your blank lines are oppositie to PEP8: http://www.python.org/dev/peps/pep-0008/#blank-lines... One could take out most blank lines in functions without losing anything. Especially nested loops are visually already well-separated without blank lines. But its not a big deal.

Is anybody on this ticket running any further mathematical tests? if not -> positive review.

comment:15 in reply to: ↑ 14 Changed 6 years ago by ncohen

If speed is really an issue then you should switch to Cython, which will expand for i in range() directly into the corresponding C loop. So there isn't that much need for xrange() in Sage.

Speed is not a problem for me at the moment. I can generate Steiner Quadruples Systems on 300 vertices, and to be honest I don't even have any use for such systems in Sage right now. I just love them very much :-P

Your blank lines are oppositie to PEP8: http://www.python.org/dev/peps/pep-0008/#blank-lines... One could take out most blank lines in functions without losing anything. Especially nested loops are visually already well-separated without blank lines. But its not a big deal.

Come on.. People write rules on that ? O_O;;;

I'll try to use less blank lines in the future... But I really think that it helps make the code more readable. And a blank line only weight 1 byte :-P

Nathann

comment:16 Changed 6 years ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

It might make it more readable for you since you know the big picture. But if you see the code for the first time you'll want to get an overview, and not wasting vertical screen estate is essential for that.

comment:17 Changed 6 years ago by jdemeyer

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