Opened 11 years ago

Closed 10 years ago

#11624 closed enhancement (fixed)

List Sidon g-sets

Reported by: mraum Owned by: sage-combinat
Priority: minor Milestone: sage-4.7.2
Component: combinatorics Keywords:
Cc: Merged in: sage-4.7.2.alpha2
Authors: Martin Raum Reviewers: Nicolas Borie
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by jdemeyer)

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

Apply:

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

Attachments (4)

trac-11624-sidon_sets.patch (2.8 KB) - added by mraum 11 years ago.
trac-11624-sidon_sets-v2.patch (3.4 KB) - added by mraum 11 years ago.
trac-11624-sidon_sets-review.patch (5.9 KB) - added by nborie 11 years ago.
trac-11624-sidon_sets-review2.patch (6.0 KB) - added by mraum 11 years ago.

Download all attachments as: .zip

Change History (10)

Changed 11 years ago by mraum

comment:1 Changed 11 years ago by nborie

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.

Changed 11 years ago by mraum

comment:2 Changed 11 years ago by mraum

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

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

Changed 11 years ago by nborie

comment:3 Changed 11 years ago by nborie

  • Description modified (diff)

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

Changed 11 years ago by mraum

comment:4 Changed 11 years ago by mraum

  • Description modified (diff)
  • Reviewers set to Nicolas Borie
  • Status changed from needs_review to positive_review

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!

comment:5 Changed 10 years ago by jdemeyer

  • Description modified (diff)

comment:6 Changed 10 years ago by jdemeyer

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