Opened 5 years ago

Closed 5 years ago

#16802 closed enhancement (fixed)

difference family database

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.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 5 years ago by vdelecroix

  • Branch set to u/vdelecroix/16802
  • Commit set to 3ce65b8ac3bc699a95075c33bc5ec8a6583880cb
  • Status changed from new to needs_review

Last 10 new commits:

0232b73trac #16604: OA(20,544)
e5f428dtrac #16604: Merged with 6.3.beta6
355ac2atrac #16662: OA for n=1046,1059,2164,3992,3994
15b449ctrac #16665: New OA for n=408,600,792,856,1368,2328,...
a515deetrac #16673: Three factors construction of MOLS
845de7atrac #16716: OA for n=262,950
a9608c5trac #16722: OA(17,560)
e5fc881trac #16722: Merged with 6.3.beta8
698b704trac #16757: Organize the V(m,t) vectors into a dictionary
3ce65b8trac #16802: database of difference family

comment:2 Changed 5 years ago by git

  • Commit changed from 3ce65b8ac3bc699a95075c33bc5ec8a6583880cb to e8984623ba5c4b181971e0524ca47dbe9cc204fc

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

9cbc23ctrac #16673: Three factors construction of MOLS
3fb8806trac #16673: review (one line simplicaction + doc)
3458d22trac #16673: Merged with 6.4.beta1
e48c1d3trac #16716: OA for n=262,950
b9aa228trac #16722: OA(17,560)
9a57f13trac #16757: Organize the V(m,t) vectors into a dictionary
57c00f0trac #16757: doctest simplication
e898462trac #16802: merge update #16757

comment:3 Changed 5 years ago by vdelecroix

Rebased above the positively reviewed #16757...

comment:4 follow-up: Changed 5 years ago by ncohen

  • 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 non-empty 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 modifications
    -if (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 group-specific 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 to set(), really ?....

Plus there is the "short+non-abelian 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 : new short_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 in difference_family.py not in database.py
  • isn't "too few" better than "too less" ?

Nathann

comment:5 in reply to: ↑ 4 Changed 5 years ago by vdelecroix

  • 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 modifications
    -if (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:

6518229trac #16802: database of difference family
d8f8feftrac #16802: review 1

comment:6 Changed 5 years ago by git

  • Commit changed from d8f8fef657006eef8ee4a5446d083a6cb45ae21f to c66bc2f976f39ad075c9d801d2c2e289cf6dfb81

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

c66bc2ftrac #16802: review 2

comment:7 Changed 5 years ago by vdelecroix

In the last commit:

  • remove DF_from_database and include the code in difference_family
  • remove the function orbit_representatives (remains only block_stabilizer)
  • remove the argument short_blocks from everywhere

comment:8 Changed 5 years ago by git

  • Commit changed from c66bc2f976f39ad075c9d801d2c2e289cf6dfb81 to c415a985d00e59bd0a60378e22f8f20f9df8accc

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

c415a98trac #16802: database of difference family

comment:9 Changed 5 years ago by ncohen

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*(k-1) = {} is not a multiple of (v-1) = {} (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 non-commutative 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 to tmp_counter
  • Replace the ValueError in difference_family with an AssertionError.

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 5 years ago by git

  • Commit changed from c415a985d00e59bd0a60378e22f8f20f9df8accc to 7c9184797514c8ef2e835c50a69756135174cfd6

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

7c91847trac #16802: Review

comment:11 Changed 5 years ago by git

  • Commit changed from 7c9184797514c8ef2e835c50a69756135174cfd6 to 4bd8d697cf5dd9370c1e80eab9f493f590a2c438

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

424e229trac #16763: New OA for n=189, plus some others through Vmt vectors
5ba165etrac #16763: Complete bibliographical references
f3f644dtrac #16763: code simplification
04936aatrac #16802: database of difference family
4bd8d69trac #16802: Review

comment:12 Changed 5 years ago by ncohen

  • Dependencies changed from #16757 to #16763

(rebased on top of #16763)

comment:13 Changed 5 years ago by git

  • Commit changed from 4bd8d697cf5dd9370c1e80eab9f493f590a2c438 to 3c0fa72c2995f6173ce5db8d63af224677f2077e

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

3c0fa72trac #16802: review the review

comment:14 Changed 5 years ago by vdelecroix

Hello,

I tried to address the issue you mentioned in comment:9...

Vincent

comment:15 Changed 5 years ago by git

  • Commit changed from 3c0fa72c2995f6173ce5db8d63af224677f2077e to 2b555e469673e02d96a77b1ba7763d71e3b2b922

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

2b555e4trac #16802: review the review

comment:16 Changed 5 years ago by git

  • Commit changed from 2b555e469673e02d96a77b1ba7763d71e3b2b922 to 4434d61c3cf39253bd9b6e02866daa2ee204146f

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

4434d61trac #16802: review the review

comment:17 Changed 5 years ago by ncohen

Thanks ! Positive review to this branch ! I will rebase it on top of #16763 and switch it to positive_review

Nathann

comment:18 Changed 5 years ago by ncohen

  • 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 5 years ago by vdelecroix

Thanks!!

Vincent

comment:20 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_info

Milestone? duplicate/wontfix?

comment:21 Changed 5 years ago by vdelecroix

  • Milestone set to sage-6.4
  • Status changed from needs_info to positive_review

comment:22 Changed 5 years ago by vbraun

  • Branch changed from public/16802 to 4434d61c3cf39253bd9b6e02866daa2ee204146f
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.