Opened 5 years ago

Closed 5 years ago

#16361 closed enhancement (fixed)

OA(7,66), OA(7,68), OA(8,69), OA(7,74) and OA(8,76)

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorial designs Keywords:
Cc: vdelecroix, knsam, dimpase, brett Merged in:
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 5d4607a (Commits) Commit: 5d4607aad0675c6ea4afd914796bc78d043a1600
Dependencies: #16461, #16388 Stopgaps:

Description (last modified by ncohen)

New designs, and a new "TD from PBD" construction ! Too bad this construction cannot be called automatically (yet) :-P

Nathann

Change History (21)

comment:1 Changed 5 years ago by ncohen

  • Authors set to Nathann Cohen
  • Branch set to u/ncohen/16361
  • Status changed from new to needs_review

comment:2 Changed 5 years ago by git

  • Commit set to 20ef21682cfe8b6532e2e2621b88d921236528f2

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

973b926trac #16236: Merged with #16272
37681e2trac #16295 : Faster is_orthogonal_array
994324etrac #16295: Doctests and review
fc6de73trac #16295: Merged with 6.3.beta1
b9f8b03trac #16295: bugfix in wilson's construction
f969003trac #16356: MOLS for n=18,57,154,276,298,342
20ef216trac #16361: OA(7,66), OA(7,68), OA(8,69), OA(7,74) and OA(8,76)

comment:3 Changed 5 years ago by ncohen

  • Component changed from combinatorics to combinatorial designs

comment:4 Changed 5 years ago by ncohen

  • Description modified (diff)

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

  • Status changed from needs_review to needs_work

Hi Nathann,

The function OA_from_PBD is sensitive to the output of orthogonal_array. More precisely, the function needs a TD(k,i) - i TD(k,1). But right now, it is just a matter of luck whether the answer of orthogonal_array(k,i) actually is... and tomorrow the answer might change. So you could not rely on that. For the current purpose of the ticket, a fix would be to feed explicitly the function OA_from_PBD with the corresponding list of TD(k,i) - i TD(k,1).

Vincent

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

Hellooooooooo !!

The function OA_from_PBD is sensitive to the output of orthogonal_array.

Indeed. And sensitive to the labelling of the design, which I guess is what bothers you.

More precisely, the function needs a TD(k,i) - i TD(k,1). But right now, it is just a matter of luck whether the answer of orthogonal_array(k,i) actually is... and tomorrow the answer might change. So you could not rely on that. For the current purpose of the ticket, a fix would be to feed explicitly the function OA_from_PBD with the corresponding list of TD(k,i) - i TD(k,1).

First, it is not true that "this can change and that I cannot rely on that" because there is a doctest. So if the constructions for which we need OA_from_PBD work now, they will continue working for as long as the doctest is there.

Secondly, you are right that the least we can do is solve this problem "up to relabelling" of the original design. This is what is being done in #16391 (it depends on #16370), which also implements another technique to find TD(k,n)-x.TD(k,1). This patch #16391 is also a dependency of #16347 (wilson's construction), and the patch on which we talk right now is also a dependency of #16347 (wilson's construction). You can see that in Wilson's construction the lines that are a problem to you have been changed and that the function OA_with_holes is called instead.

+    # Building the OA
+    OAs ={i:list(OA_with_holes(k,i,i)) for i in K}
+
+    # Turning them into IMOLS
+    for i,OA in OAs.items():
+        for ii in range(i):
+            OAs[i].remove((ii,)*k)

Sooooooooooo given that 1) the current construction will work for as long as they are doctested 2) What bothers you is already fix a bit above

ittttttt would be cool if you could consider that this problem does not matter as it is already fixed above. It just comes from the fact that I write all my code in the same file but that I try to split it into small bits that are easier to review... And in this case I probably removed the call to OA_with_PBD so that this patch could be reviewed without the "Helper functions" patch as a dependency.

Nathann

Last edited 5 years ago by ncohen (previous) (diff)

comment:7 Changed 5 years ago by ncohen

  • Status changed from needs_work to needs_review

comment:8 Changed 5 years ago by vdelecroix

EDIT: post removed

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:9 follow-up: Changed 5 years ago by vdelecroix

Hello,

incomplete_orthogonal_array:

  • Under the condition x <= 3 and n > k-1 and k >= 3 it should return orthogonal_array(k,n,existence=True) and not True.
  • If k=n+1 then we have a projective planes and all blocks intersect... so there is no OA(n+1,n) - 2.OA(n+1,1). I added the appropriate test in incomplete_orthogonal_array.

OA_from_PBD:

  • it makes more sense to use the function incomplete_orthogonal_array since it is here!!
  • I changed the end of the if/elif to forward the non-existence (and also avoid doctest error because of #16388)
  • I changed the doctest (which was just a copy of the one in database.py!!) to be something non-trivial

see the changes on the branch public/16361 (where #16461 is merged). I was able to build the doc and all test pass...

Do you have further remarks? Otherwise it deserves a positive review.

Vincent

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

Hello !

incomplete_orthogonal_array:

  • Under the condition x <= 3 and n > k-1 and k >= 3 it should return orthogonal_array(k,n,existence=True) and not True.

+1

  • If k=n+1 then we have a projective planes and all blocks intersect... so there is no OA(n+1,n) - 2.OA(n+1,1). I added the appropriate test in incomplete_orthogonal_array.

See [1]

OA_from_PBD:

  • it makes more sense to use the function incomplete_orthogonal_array since it is here!!

+1

  • I changed the end of the if/elif to forward the non-existence (and also avoid doctest error because of #16388)

See below

  • I changed the doctest (which was just a copy of the one in database.py!!) to be something non-trivial

+1

see the changes on the branch public/16361 (where #16461 is merged). I was able to build the doc and all test pass...

Do you have further remarks? Otherwise it deserves a positive review.

Well... Actually, I think that you should not intercept all exceptions in order to return specific error messages... I believe that you should let the subfunction raise its own exception. That's going too far I think :-/

If the user requests a construction that requires other construction, let the other constructions raise an exception ! The user will see a message like "Impossible to build a OA(....)", meaning that the function needed one and it did not exist.

+    for i in K:
+        if incomplete_orthogonal_array(k,i,(1,)*i,existence=True) is False:
+            raise EmptySetError("The construction is impossible since there is no OA({},{})-{}.OA({},1)".format(k,i,i,k))
+        elif incomplete_orthogonal_array(k,i,(1,)*i,existence=True) is Unknown:
+            raise NotImplementedError("I was not able to build an OA({},{})-{}.OA({},1)".format(k,i,i,k))
+        else:
+            OAs[i] = incomplete_orthogonal_array(k,i,(1,)*i)

In the first two situations, you return manually the exception that should be raised by incomplete_orthogonal_array. Why do it again manually ? Why not just call it ?

Same here

+    elif orthogonal_array(k,n,existence=existence) is False:
+        if existence:
+            return False
+        raise EmptySetError("There is no OA({},{}) and hence no OA({},{})-{}.OA({},1)".format(k,n,k,n,k))
+
+    elif orthogonal_array(k,n,existence=existence) is Unknown:
+        if existence:
+            return Unknown
+        raise NotImplementedError("I do not know how to build this OA({},{})-{}.OA({},1)".format(k,n,k))
+
     else:
-        return orthogonal_array(k,n,existence=existence)
+        raise RuntimeError("This should not happen!")

The line you removed was doing the very same job, i.e. forwarding the non-existence results ! All you did was rewrite the exception, and the user sees :

"There is no OA(k,n) and this no OA(k,n)-xOA(k,1)"

instead of

"There is no OA(k,n)"

I believe that you should let the subfunction raise its exception. What do you think ?

Nathann

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

Replying to ncohen:

Hello !

incomplete_orthogonal_array:

  • If k=n+1 then we have a projective planes and all blocks intersect... so there is no OA(n+1,n) - 2.OA(n+1,1). I added the appropriate test in incomplete_orthogonal_array.

See [1]

What is [1]?

OA_from_PBD:

  • I changed the end of the if/elif to forward the non-existence (and also avoid doctest error because of #16388)

See below

see the changes on the branch public/16361 (where #16461 is merged). I was able to build the doc and all test pass...

Do you have further remarks? Otherwise it deserves a positive review.

Well... Actually, I think that you should not intercept all exceptions in order to return specific error messages... I believe that you should let the subfunction raise its own exception. That's going too far I think :-/

I believe that you should let the subfunction raise its exception. What do you think ?

All right, but then you should put #16388 as a dependency and adapt the doctests...

Vincent

comment:12 Changed 5 years ago by git

  • Commit changed from 20ef21682cfe8b6532e2e2621b88d921236528f2 to 02ecf51a3101880f34db39cf4ed38f19c7fd34f3

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

4007157trac #16361: merge with #16461
191aaabtrac #16361: fix bug in IOA + better OA_from_PBD
0380eadtrac #16461: fix documentation
8704b9ctrac #16361: merge updated #16461
767e091trac #16388: Specify the values of k,n in the exceptions
a460169merge Sage version 6.3.beta3
c365a39trac #16388: use format for OA + specify (k,n) for BIBD
ec26ca2trac #16388: a missing one in BIBD_from_TD
79178b6trac #16388: (v,k,1)-BIBD instead of BIBD(v,k,1)
02ecf51trac #16361: Merged with #16388

comment:13 Changed 5 years ago by git

  • Commit changed from 02ecf51a3101880f34db39cf4ed38f19c7fd34f3 to 5d4607aad0675c6ea4afd914796bc78d043a1600

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

5d4607atrac #16361: Don't re-raise the exceptions

comment:14 Changed 5 years ago by ncohen

Here it is !

Nathann

comment:15 follow-up: Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Hi,

Looks good to me. All test pass and documentation builds!

Do you know if there is an OA(n,n) for some n which is not a prime power? (it is not in Sage).

Vincent

comment:16 in reply to: ↑ 15 Changed 5 years ago by ncohen

Yo !

Looks good to me. All test pass and documentation builds!

I hope that Volker will merge it soon... I had not noticed that some tickets had been closed already in an unreleased beta :-/

Do you know if there is an OA(n,n) for some n which is not a prime power? (it is not in Sage).

HMmmm.... No idea, but there is a partial answer as Theorem III.3.32 in the handbook. Looks like we will call "is_sum_of_squares" again :-P

Nathann

comment:17 Changed 5 years ago by ncohen

  • Dependencies changed from #16356 to #16461, #16388

comment:18 follow-up: Changed 5 years ago by vbraun

Reviewer name

Whats up with the TODO?

comment:19 in reply to: ↑ 18 Changed 5 years ago by ncohen

  • Reviewers set to Vincent Delecroix

Whats up with the TODO?

Sorry, it was a "note to self". I did that when I rebased everything above.

Nathann

comment:20 Changed 5 years ago by ncohen

  • Description modified (diff)

comment:21 Changed 5 years ago by vbraun

  • Branch changed from u/ncohen/16361 to 5d4607aad0675c6ea4afd914796bc78d043a1600
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.