Opened 6 years ago
Closed 6 years ago
#16802 closed enhancement (fixed)
difference family database
Reported by:  vdelecroix  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  combinatorial designs  Keywords:  
Cc:  ncohen  Merged in:  
Authors:  Vincent Delecroix  Reviewers:  Nathann Cohen 
Report Upstream:  N/A  Work issues:  
Branch:  4434d61 (Commits)  Commit:  4434d61c3cf39253bd9b6e02866daa2ee204146f 
Dependencies:  #16763  Stopgaps: 
Description
Import the database from the Handbook of combinatorial design inside Sage.
Change History (22)
comment:1 Changed 6 years ago by
 Branch set to u/vdelecroix/16802
 Commit set to 3ce65b8ac3bc699a95075c33bc5ec8a6583880cb
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Commit changed from 3ce65b8ac3bc699a95075c33bc5ec8a6583880cb to e8984623ba5c4b181971e0524ca47dbe9cc204fc
Branch pushed to git repo; I updated commit sha1. New commits:
9cbc23c  trac #16673: Three factors construction of MOLS

3fb8806  trac #16673: review (one line simplicaction + doc)

3458d22  trac #16673: Merged with 6.4.beta1

e48c1d3  trac #16716: OA for n=262,950

b9aa228  trac #16722: OA(17,560)

9a57f13  trac #16757: Organize the V(m,t) vectors into a dictionary

57c00f0  trac #16757: doctest simplication

e898462  trac #16802: merge update #16757

comment:3 Changed 6 years ago by
Rebased above the positively reviewed #16757...
comment:4 followup: ↓ 5 Changed 6 years ago by
 Status changed from needs_review to needs_work
Yooooooooooooooooooooooooooooo !!!!
First review of this patch (it will be clearer after those points have been solved):
 The DF in the database: why add a 'S' in the *blocks* of short groups ? it is not like it is hard to check that a block has an nonempty stabilizer. We can get this info easily. Plus those 'S' have nothing to do in the blocks of a design ...
 The database looks a bit messy as it is. Could you align some stuff, like the ':' or the ',' so that one can actually read it in the code ?
 The database should be indexed with
(v,k,l)
instead of((v1,v2,v3),k,l)
. You can have something like that:
DF_database = { (v,k,l) : { (v1,v2,v3): [DF1,DF2,DF3,....] } }
This way you can easily check whether there exists a BIBD that can be obtained from a difference family. And you can also find
(v1,v2,v3)
easily.
 With a database indexed with
(v,k,l)
you can undo those modificationsif (v,k,l) in DF_constructions: +G_df = DF_from_database(v,k,l,short_blocks=short_blocks) +if G_df:
 Block stabilizer: instead of computing the stabilizer of blocks, you could
just develop a block with respect to the group and remove duplicated, you know
? All it takes is a simple call to
set(...)
. Much easier to understand, no questions about where all those groupspecific functions should be implemented...
If you do that you save around 100 lines of code+doc with the three functions
block_stabilizer, orbit_representatives, partial_differences
. Really I would have nothing if those functions were group methods, but having to implement all that just for difference families, and just to avoid a call toset()
, really ?....
Plus there is the "short+nonabelian exception" in
is_difference_family
, that wouldn't be needed anymore in this case ....
 If you insist on having all those functions to avoid calling "set" to simplify the orbits of a block, and if you want to keep the warning above, you may also have to handle the case where the group is a multiplicative+commutative group.
 (That's going very far just to avoid a
set(...)
:P
difference_family
: newshort_blocks
argument. Really, WHY do you care so much about short blocks ? They are just blocks whose orbit is smaller, what's all the fuss about ? If we give the users access to the database, can't we just give them a function that tests if a block is short and let them do what they want with it ?
 What's the point of filtering difference families with short blocks anyway ?
 The checks in
DF_from_database
: if you want to check anything about the database, it would be better to do it in the doctests than at runtime ?...
DF_from_database
: if you actually need it, should be indifference_family.py
not indatabase.py
 isn't "too few" better than "too less" ?
Nathann
comment:5 in reply to: ↑ 4 Changed 6 years ago by
 Branch changed from u/vdelecroix/16802 to public/16802
 Commit changed from e8984623ba5c4b181971e0524ca47dbe9cc204fc to d8f8fef657006eef8ee4a5446d083a6cb45ae21f
 Status changed from needs_work to needs_review
Thanks for the rebase.
Replying to ncohen:
Yooooooooooooooooooooooooooooo !!!!
First review of this patch (it will be clearer after those points have been solved):
 The DF in the database: why add a 'S' in the *blocks* of short groups ?
removed
 The database looks a bit messy as it is. Could you align some stuff, like the ':' or the ',' so that one can actually read it in the code ?
 The database should be indexed with
(v,k,l)
instead of((v1,v2,v3),k,l)
. With a database indexed with
(v,k,l)
you can undo those modificationsif (v,k,l) in DF_constructions: +G_df = DF_from_database(v,k,l,short_blocks=short_blocks) +if G_df:
done, done, done.
For the rest, some people defines difference families with short blocks (as in the Handbook) and some people do not allow them (like in Stinson for example). So you have to care about the two definitions.
About the functions block_stabilizer, orbit_representatives, partial_differences
it is used in basically two places: is_difference_family
and BIBID_from_difference_family
. You can not avoid them in the former. Nevertheless:
 I removed
partial_differences
as it was used in only one place and is a two lines function  I rewrote some of the doc
As you can see, the is_difference_family
is very detailed and it was very useful to debug the database from the Handbook.
I do not see the need of multiplicative Abelian group in difference families...
Vincent
New commits:
6518229  trac #16802: database of difference family

d8f8fef  trac #16802: review 1

comment:6 Changed 6 years ago by
 Commit changed from d8f8fef657006eef8ee4a5446d083a6cb45ae21f to c66bc2f976f39ad075c9d801d2c2e289cf6dfb81
Branch pushed to git repo; I updated commit sha1. New commits:
c66bc2f  trac #16802: review 2

comment:7 Changed 6 years ago by
In the last commit:
 remove
DF_from_database
and include the code indifference_family
 remove the function
orbit_representatives
(remains onlyblock_stabilizer
)  remove the argument
short_blocks
from everywhere
comment:8 Changed 6 years ago by
 Commit changed from c66bc2f976f39ad075c9d801d2c2e289cf6dfb81 to c415a985d00e59bd0a60378e22f8f20f9df8accc
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
c415a98  trac #16802: database of difference family

comment:9 Changed 6 years ago by
Helloooooooooooo !!!
Very good code, efficient and all. I added a commit but I still have a couple of remarks :
 What does that mean ?
+An example with a short block (i.e. considering restricted difference when a +block has a non trivial stabilizer)::
 I do not find the two messages about the checks over l very clear for a user:
sum(1/s_i) k*(k1) = {} is not a multiple of (v1) = {} (stabilizer sizes {})
The si are not defined (and it is hard to define them in an error message)... What would you think of formulating that with BIBD terminology ? A bit like my comment about nb_diff in the code ?
 What do we do about noncommutative groups ? If we don't handle them it would be nice to have an error message sayng "the group is not commutative". And if we handle them we have to be more verbose about left/right actions and everything (I personally think that it is going too far, but well)..
I did several things in my commit:
 move a DF that was not properly ordered
 expand the doc a bit in some places
 Removed the "abelian/additive" in
is_difference_family
, but that's also part of the more general question above.
 rename
c_counter
totmp_counter
 Replace the
ValueError
indifference_family
with anAssertionError
.
Tell me if you agree with those changes, and what you think of my questions above. Before we set this ticket to positive_review
I will rebase it somehow, so that all design patches are linearly ordered.
Thanks !
Nathann
comment:10 Changed 6 years ago by
 Commit changed from c415a985d00e59bd0a60378e22f8f20f9df8accc to 7c9184797514c8ef2e835c50a69756135174cfd6
Branch pushed to git repo; I updated commit sha1. New commits:
7c91847  trac #16802: Review

comment:11 Changed 6 years ago by
 Commit changed from 7c9184797514c8ef2e835c50a69756135174cfd6 to 4bd8d697cf5dd9370c1e80eab9f493f590a2c438
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
424e229  trac #16763: New OA for n=189, plus some others through Vmt vectors

5ba165e  trac #16763: Complete bibliographical references

f3f644d  trac #16763: code simplification

04936aa  trac #16802: database of difference family

4bd8d69  trac #16802: Review

comment:12 Changed 6 years ago by
 Dependencies changed from #16757 to #16763
(rebased on top of #16763)
comment:13 Changed 6 years ago by
 Commit changed from 4bd8d697cf5dd9370c1e80eab9f493f590a2c438 to 3c0fa72c2995f6173ce5db8d63af224677f2077e
Branch pushed to git repo; I updated commit sha1. New commits:
3c0fa72  trac #16802: review the review

comment:14 Changed 6 years ago by
comment:15 Changed 6 years ago by
 Commit changed from 3c0fa72c2995f6173ce5db8d63af224677f2077e to 2b555e469673e02d96a77b1ba7763d71e3b2b922
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
2b555e4  trac #16802: review the review

comment:16 Changed 6 years ago by
 Commit changed from 2b555e469673e02d96a77b1ba7763d71e3b2b922 to 4434d61c3cf39253bd9b6e02866daa2ee204146f
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
4434d61  trac #16802: review the review

comment:17 Changed 6 years ago by
Thanks ! Positive review to this branch ! I will rebase it on top of #16763 and switch it to positive_review
Nathann
comment:18 Changed 6 years ago by
 Reviewers set to Nathann Cohen
 Status changed from needs_review to positive_review
Oh. Looks like I did it already. Let's go then ! :P
Nathann
comment:19 Changed 6 years ago by
Thanks!!
Vincent
comment:20 Changed 6 years ago by
 Status changed from positive_review to needs_info
Milestone? duplicate/wontfix?
comment:21 Changed 6 years ago by
 Milestone set to sage6.4
 Status changed from needs_info to positive_review
comment:22 Changed 6 years ago by
 Branch changed from public/16802 to 4434d61c3cf39253bd9b6e02866daa2ee204146f
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits:
trac #16604: OA(20,544)
trac #16604: Merged with 6.3.beta6
trac #16662: OA for n=1046,1059,2164,3992,3994
trac #16665: New OA for n=408,600,792,856,1368,2328,...
trac #16673: Three factors construction of MOLS
trac #16716: OA for n=262,950
trac #16722: OA(17,560)
trac #16722: Merged with 6.3.beta8
trac #16757: Organize the V(m,t) vectors into a dictionary
trac #16802: database of difference family