List Sidon g-sets

[sagetrac-mraum]

The attached patch provides a recursive algorithm that lists Sidon g-sets with elements of to a natural number N.

Apply:

1. attachment: trac-11624-sidon_sets-v2.patch
2. attachment: trac-11624-sidon_sets-review2.patch

Component: combinatorics

Author: Martin Raum

Reviewer: Nicolas Borie

Merged: sage-4.7.2.alpha2

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

[sagetrac-nborie]

comment:1

Attachment: trac-11624-sidon_sets.patch.gz

Hello,

I downloaded the patch, it applied and worked well.

I never played with Sidon sets before and know relatively nothing about them. I did that as first computation :

sage: [len(sidon_sets(i)) for i in range(1,21)]
[2, 4, 6, 10, 14, 20, 26, 36, 46, 60, 74, 94, 114, 140, 166, 202, 238, 284, 330, 390]

And asked the Sloane for what does it look like :

Number of binary partitions: number of partitions of 2n into powers of 2.

So, is there a bug in the algorithm or I am perhaps missing something... It seems to me that the algorithm miss some Sidon sets. I don't really know...

For example, Sloane tell that [1,2,4,8,13] is a Sidon set but currently the algorithm returns:

sage: max([len(S) for S in sidon_sets(13)])
4

On the technical point of view, the sage code convention is to indent by block of 4 spaces. don't use tabulation... It should look like that:

def bla():
    r"""
    Some doc

    EXAMPLES::

        sage: some example

    TESTS::

        sage: some test

There is a micro typo line 44 of the patch -> Valuerror

Sorry for my poor English... Put the status "needs review" when you will feel the job is finish from your side. This will be a nice add.

Cheers,
Nicolas.

[sagetrac-mraum]

comment:2

Attachment: trac-11624-sidon_sets-v2.patch.gz

Sorry for this. That were two stupid mistakes, that could have been easily caught by better testing. I added the tests for the exceptions and I checked that the Sidon set that was missing before is found now.
I also corrected the documentation, that I was too lazy with.

Apply: trac-11624-sidon_sets-v2.patch

[sagetrac-nborie]

Attachment: trac-11624-sidon_sets-review.patch.gz

[sagetrac-nborie]

comment:3

Thanks for being so quick...

I propose you a reviewer patch in which I had some tests and some documentations, I link the file to the rst combinat tree for the built doc, I categorifyed from the python frozenset feature to sage categories. I also put the clever code in a slave cached function because sphinx didn't want to build documentation of any cached function.

I checked that sage -docbuild reference html give an acceptable printout.

Tell me if you're agree with such change, feel free to improve my words in English (and correct mistakes if you find some...). Categories are a little bit technical but it really make us win a lot. They gives some coherence, factorize the code and allow us to use functorial construction, see for example :

sage: S = sidon_sets(3, 2)
sage: TestSuite(S).run(verbose=True)
running ._test_an_element() . . .
  self.an_element doesn't have any parent

  The set doesn't seems to implement __call__; skipping test of construction idempotency
 pass
running ._test_category() . . . pass
running ._test_elements() . . .
  Running the test suite of self.an_element()
  running ._test_an_element() . . .
  The set doesn't seems to implement __call__; skipping test of construction idempotency
 pass
  running ._test_category() . . . pass
  running ._test_elements() . . .
  Running the test suite of self.an_element()
    running ._test_category() . . . pass
    running ._test_eq() . . . pass
    running ._test_not_implemented_methods() . . . pass
    running ._test_pickling() . . . pass
    pass
  running ._test_elements_eq() . . . pass
  running ._test_eq() . . . pass
  running ._test_not_implemented_methods() . . . pass
  running ._test_pickling() . . . pass
  running ._test_some_elements() . . . pass
  pass
running ._test_elements_eq() . . . pass
running ._test_eq() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_pickling() . . . pass
running ._test_some_elements() . . . pass
sage: A = S.algebra(QQ)
sage: A
Free module generated by {{2}, {3}, {1, 2}, {}, {2, 3}, {1}, {1, 3}, {1, 2, 3}} over Rational Field
sage: A.an_element()
2*B[{3}] + 2*B[{2}] + 3*B[{1, 2}]

To state if this feature is correct with what you want, just read 'Set??', all the magic is inside that.

Apply:

1. trac-11624-sidon_sets-v2.patch
2. trac-11624-sidon_sets-review.patch

[sagetrac-mraum]

comment:4

Attachment: trac-11624-sidon_sets-review2.patch.gz

Perfect! I only updated the spelling of few words and left all other changes untouched. I think it is indeed a good idea to categorify this, even though, initially, I didn't for fear of performance loss.

Thanks for that awesomely quick review!

[sagetrac-mraum]

Reviewer: Nicolas Borie

[jdemeyer]

Merged: sage-4.7.2.alpha2