Opened 4 years ago

Closed 4 years ago

#17581 closed enhancement (fixed)

resolvable BIBD

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.5
Component: combinatorial designs Keywords:
Cc: vdelecroix, dimpase Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 3e25827 (Commits) Commit: 3e25827aae4d94fe98919afd6eabe7398059fda5
Dependencies: Stopgaps:

Description

This branch adds resolvable_bibd.py to combinat/designs/. It contains a couple of constructions for resolvable (v,k,1)-BIBD when k=3,4.

Not all RBIBD with k=3,4 can be built, but I have on my computer the general construction for RBIBD with k=3. This is part of it, and the rest will follow in small pieces, as there are many "design questions" involved.

Nathann

Change History (17)

comment:1 Changed 4 years ago by ncohen

  • Branch set to public/17581
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by git

  • Commit set to 6abc364f4fd25e4f6bbc3e24b1d7f9dbf5ddc51e

Branch pushed to git repo; I updated commit sha1. New commits:

6abc364trac #17581: Resolvable BIBD

comment:3 Changed 4 years ago by git

  • Commit changed from 6abc364f4fd25e4f6bbc3e24b1d7f9dbf5ddc51e to 1235bad6ae59f20d6ecb160c2126a9c6b134d7bb

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1235badtrac #17581: Resolvable BIBD

comment:4 follow-up: Changed 4 years ago by vdelecroix

Hello Nathann,

1) What's the point of

-Balanced Incomplete Block Designs (BIBD)
+(BIBD) Balanced Incomplete Block Designs

I prefer the former.

2) Do you know if difference family/difference set can be used to generate RBIBD? (It seems to be no, I will think about it)

will continue later. Vincent

comment:5 in reply to: ↑ 4 ; follow-up: Changed 4 years ago by ncohen

Yooooooo !

1) What's the point of

-Balanced Incomplete Block Designs (BIBD)
+(BIBD) Balanced Incomplete Block Designs

I prefer the former.

Oh. I made that change because ultimately it will be easier to read in this page:

http://www.sagemath.org/doc/reference/combinat/designs.html

The lines will begin with BIBD/BIBD,GDD, i.e. the signs that we are used to see and spot easily.

2) Do you know if difference family/difference set can be used to generate RBIBD? (It seems to be no, I will think about it)

I think that I saw something like that in the Beth/Jungnickel/Lenz book I sent you. No clearer memory, sorry :-/

Nathann

comment:6 in reply to: ↑ 5 ; follow-up: Changed 4 years ago by vdelecroix

Replying to ncohen:

Yooooooo !

1) What's the point of

-Balanced Incomplete Block Designs (BIBD)
+(BIBD) Balanced Incomplete Block Designs

I prefer the former.

Oh. I made that change because ultimately it will be easier to read in this page:

http://www.sagemath.org/doc/reference/combinat/designs.html

The lines will begin with BIBD/BIBD,GDD, i.e. the signs that we are used to see and spot easily.

I do not find it easier to read. Could we stick with

Crazy Complete Name (CCN)

2) Do you know if difference family/difference set can be used to generate RBIBD? (It seems to be no, I will think about it)

I think that I saw something like that in the Beth/Jungnickel/Lenz book I sent you. No clearer memory, sorry :-/

Not simple... parallel classes do not fit very well with group actions.

Vincent

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

Yo,

I do not find it easier to read. Could we stick with

Crazy Complete Name (CCN)

If you insist.... Please tell me what other things you would like to change in this commit, I'll address all of it at once.

Not simple... parallel classes do not fit very well with group actions.

Depends.. In the constrution I have on my computer for KTS there are several designs built from difference families.

They are resolvable, but then some new points are added to build larger designs. Well, you will see.

For the moment it is not a Sage patch because there are many things in needs_review, and that writing the commit now will mean a lot of conflicts to solve later.

Nathann

comment:8 follow-up: Changed 4 years ago by vdelecroix

Hello,

See my commit at u/vdelecroix/17581.

1) Why not return an object with type BalancedIncompleteBlockDesign. That way you can add to the examples .is_resolvable(). (moreover, contrarily to the others v_4_1_rbibd does!?)

2) The lines

bla.extend([a**(i+j0),a**(i+j1),a**(i+j2)] for i in a_big_list])

are ugly... I changed a bit one of them but I am still not happy to have a quadratic complexity when linear is doable.

3) I used discrete_log where you did a while loop... should be faster.

Vincent

comment:9 Changed 4 years ago by ncohen

  • Branch changed from public/17581 to u/vdelecroix/17581
  • Commit changed from 1235bad6ae59f20d6ecb160c2126a9c6b134d7bb to 6ec96bfe78beb32322dd37792b8712432f2efd64

New commits:

6ec96bftrac #17581: doc + simplification

comment:10 in reply to: ↑ 8 ; follow-up: Changed 4 years ago by ncohen

  • Status changed from needs_review to positive_review

Yo !

See my commit at u/vdelecroix/17581.

Looks good. About the example of KTS at the beginning of the doc: I tried to write it in such a way that it is both informative and readable by users. Yours is prettier indeed, but.. Clearly harder to read. Anyway let's talk about this before it is changed, next time.

1) Why not return an object with type BalancedIncompleteBlockDesign. That way you can add to the examples .is_resolvable(). (moreover, contrarily to the others v_4_1_rbibd does!?)

I do not understand your sentence. Where isn't a BalancedIncompleteBlockDesign object returned?

2) The lines

bla.extend([a**(i+j0),a**(i+j1),a**(i+j2)] for i in a_big_list])

AHahah. Well compared to the complexity of other parts of the algorithm I am sure that it makes no difference. By the way isn't it a nlog(n) complexity ? Exponents are cheap.

3) I used discrete_log where you did a while loop... should be faster.

Oh thanks, I did not know that we had that. There must be some other spot where it is needed in the code then, for I am sure that I missed it once at least.

Assuming that you see nothing else to change, I set this ticket to positive_review. Thanks for your help again, there would be no design code in Sage if not for that ^^;

Nathann

comment:11 in reply to: ↑ 10 ; follow-up: Changed 4 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from positive_review to needs_work

Replying to ncohen:

Yo !

See my commit at u/vdelecroix/17581.

Looks good. About the example of KTS at the beginning of the doc: I tried to write it in such a way that it is both informative and readable by users. Yours is prettier indeed, but.. Clearly harder to read. Anyway let's talk about this before it is changed, next time.

Right. I found it so ugly...

1) Why not return an object with type BalancedIncompleteBlockDesign. That way you can add to the examples .is_resolvable(). (moreover, contrarily to the others v_4_1_rbibd does!?)

I do not understand your sentence. Where isn't a BalancedIncompleteBlockDesign object returned?

look at the case for k=2 in resolvable_balanced_incomplete_block_design. And by the way

sage: KTS = designs.resolvable_balanced_incomplete_block_design(8,2); KTS
Traceback (most recent call last):
...
TypeError: unhashable type: 'list'

2) The lines

bla.extend([a**(i+j0),a**(i+j1),a**(i+j2)] for i in a_big_list])

AHahah. Well compared to the complexity of other parts of the algorithm I am sure that it makes no difference. By the way isn't it a nlog(n) complexity ? Exponents are cheap.

Right. These are n log(n), I realized that after I put on "submit changes".

3) I used discrete_log where you did a while loop... should be faster.

Oh thanks, I did not know that we had that. There must be some other spot where it is needed in the code then, for I am sure that I missed it once at least.

Hum, strange. That you who spot these to me in a previous ticket ;-)

Assuming that you see nothing else to change, I set this ticket to positive_review. Thanks for your help again, there would be no design code in Sage if not for that ^^;

Please fix the case k=2

Vincent

comment:12 in reply to: ↑ 11 ; follow-up: Changed 4 years ago by ncohen

Yo !

look at the case for k=2 in resolvable_balanced_incomplete_block_design. And by the way

Okay, that was a bug and actually there were other bugs. It is fixed with this commit. This being said I still do not understand why you say that some part of the code does not return a BIBD, so I wouldn't mind if you could tell me exactly what the problem is.

Nathann

comment:13 Changed 4 years ago by ncohen

  • Branch changed from u/vdelecroix/17581 to public/17581
  • Commit changed from 6ec96bfe78beb32322dd37792b8712432f2efd64 to 3e25827aae4d94fe98919afd6eabe7398059fda5
  • Status changed from needs_work to needs_review

New commits:

2ccc198trac #17581: Merged with 6.5.beta5
3e25827trac #17581: Bugfix

comment:14 in reply to: ↑ 12 ; follow-up: Changed 4 years ago by vdelecroix

Replying to ncohen:

Yo !

look at the case for k=2 in resolvable_balanced_incomplete_block_design. And by the way

Okay, that was a bug and actually there were other bugs. It is fixed with this commit. This being said I still do not understand why you say that some part of the code does not return a BIBD, so I wouldn't mind if you could tell me exactly what the problem is.

It was precisely the case k=2 which did not

classes = B._classes
return classes

Vincent

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

It was precisely the case k=2 which did not

classes = B._classes
return classes

Nope. I still don't get it. There is not a single occurrence of "return classes" in the file.

Nathann

comment:16 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Sorry, I was being stupid.

Vincent

comment:17 Changed 4 years ago by vbraun

  • Branch changed from public/17581 to 3e25827aae4d94fe98919afd6eabe7398059fda5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.