Opened 6 years ago
Closed 6 years ago
#17581 closed enhancement (fixed)
resolvable BIBD
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.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 6 years ago by
 Branch set to public/17581
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Commit set to 6abc364f4fd25e4f6bbc3e24b1d7f9dbf5ddc51e
comment:3 Changed 6 years ago by
 Commit changed from 6abc364f4fd25e4f6bbc3e24b1d7f9dbf5ddc51e to 1235bad6ae59f20d6ecb160c2126a9c6b134d7bb
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
1235bad  trac #17581: Resolvable BIBD

comment:4 followup: ↓ 5 Changed 6 years ago by
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 ; followup: ↓ 6 Changed 6 years ago by
Yooooooo !
1) What's the point of
Balanced Incomplete Block Designs (BIBD) +(BIBD) Balanced Incomplete Block DesignsI 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 ; followup: ↓ 7 Changed 6 years ago by
Replying to ncohen:
Yooooooo !
1) What's the point of
Balanced Incomplete Block Designs (BIBD) +(BIBD) Balanced Incomplete Block DesignsI 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 6 years ago by
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 followup: ↓ 10 Changed 6 years ago by
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 6 years ago by
 Branch changed from public/17581 to u/vdelecroix/17581
 Commit changed from 1235bad6ae59f20d6ecb160c2126a9c6b134d7bb to 6ec96bfe78beb32322dd37792b8712432f2efd64
New commits:
6ec96bf  trac #17581: doc + simplification

comment:10 in reply to: ↑ 8 ; followup: ↓ 11 Changed 6 years ago by
 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 othersv_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 awhile
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 ; followup: ↓ 12 Changed 6 years ago by
 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 othersv_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 awhile
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 ; followup: ↓ 14 Changed 6 years ago by
Yo !
look at the case for
k=2
inresolvable_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 6 years ago by
 Branch changed from u/vdelecroix/17581 to public/17581
 Commit changed from 6ec96bfe78beb32322dd37792b8712432f2efd64 to 3e25827aae4d94fe98919afd6eabe7398059fda5
 Status changed from needs_work to needs_review
comment:14 in reply to: ↑ 12 ; followup: ↓ 15 Changed 6 years ago by
Replying to ncohen:
Yo !
look at the case for
k=2
inresolvable_balanced_incomplete_block_design
. And by the wayOkay, 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 6 years ago by
It was precisely the case
k=2
which did notclasses = 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 6 years ago by
 Status changed from needs_review to positive_review
Sorry, I was being stupid.
Vincent
comment:17 Changed 6 years ago by
 Branch changed from public/17581 to 3e25827aae4d94fe98919afd6eabe7398059fda5
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
trac #17581: Resolvable BIBD