Sage: Ticket #15310: Wilson's construction of Transversal Designs/Orthogonal Arrays/MOLS
https://trac.sagemath.org/ticket/15310
<p>
This ticket implements Wilson's construction of transversal designs (which are equivalent to OA and MOLS) as found in Douglas Stinson's book.
</p>
<p>
The implementation of the construction is not a very technical problem though it requires several parameters that are not obvious when the user asks for a transversal design of parameters <code>k,n</code>. A function <code>find_wilson_decomposition</code> thus tries to guess those parameters, and needs for that to know the values of <code>k,n</code> for which Sage knows how to build a transversal design.
</p>
<p>
It can then try all possibilities, and use Wilson's construction as efficiently as possible !
</p>
<p>
Nathann
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15310
Trac 1.1.6ncohenSun, 20 Oct 2013 17:53:12 GMTcommit, branch set
https://trac.sagemath.org/ticket/15310#comment:1
https://trac.sagemath.org/ticket/15310#comment:1
<ul>
<li><strong>commit</strong>
set to <em>21ca843b9a004e8e22e1a90ebbfbfedf968f9ad8</em>
</li>
<li><strong>branch</strong>
set to <em>u/ncohen/15310</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td>[changeset:21ca843]</td><td>Wilson's construction of Transversal <a class="missing wiki">Designs/Orthogonal?</a> Arrays/MOLS
</td></tr><tr><td>[changeset:7c1b651]</td><td>Orthogonal arrays
</td></tr><tr><td>[changeset:d93abcd]</td><td>Latin Squares
</td></tr><tr><td>[changeset:2ec76c7]</td><td>Bug in <a class="missing wiki">AffineGeometryDesign?</a>
</td></tr><tr><td>[changeset:cf71d58]</td><td>Rebase on 5.13.beta0
</td></tr><tr><td>[changeset:9fcfb13]</td><td>Rename the method from <a class="missing wiki">ProjectivePlaneDesign?</a> to <a class="missing wiki">DesarguesianProjectivePlaneDesign?</a>
</td></tr><tr><td>[changeset:363badb]</td><td>trac 15107 -- reviewer's comments
</td></tr><tr><td>[changeset:ee6d412]</td><td>Projective Plane designs constructor
</td></tr></table>
TicketgitTue, 22 Oct 2013 13:24:19 GMTcommit changed
https://trac.sagemath.org/ticket/15310#comment:2
https://trac.sagemath.org/ticket/15310#comment:2
<ul>
<li><strong>commit</strong>
changed from <em>21ca843b9a004e8e22e1a90ebbfbfedf968f9ad8</em> to <em>7487b62fe657ef04722f06fa5c1e7647855e4f89</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td>[changeset:7487b62]</td><td>Wilson's construction -- find_wilson_decomposition and test of availability
</td></tr><tr><td>[changeset:847c7b6]</td><td>Wilson's construction -- rebase on bugfix from 15287
</td></tr><tr><td>[changeset:59f340b]</td><td>Orthogonal arrays -- doctest
</td></tr><tr><td>[changeset:e32c6de]</td><td>Orthogonal arrays -- bugfix
</td></tr></table>
TicketncohenTue, 22 Oct 2013 13:25:12 GMTstatus changed; dependencies set
https://trac.sagemath.org/ticket/15310#comment:3
https://trac.sagemath.org/ticket/15310#comment:3
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>dependencies</strong>
set to <em>#15287</em>
</li>
</ul>
TicketncohenTue, 22 Oct 2013 13:31:36 GMTdescription changed
https://trac.sagemath.org/ticket/15310#comment:4
https://trac.sagemath.org/ticket/15310#comment:4
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15310?action=diff&version=4">diff</a>)
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/15310#comment:5
https://trac.sagemath.org/ticket/15310#comment:5
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketgitThu, 03 Apr 2014 14:31:10 GMTcommit changed
https://trac.sagemath.org/ticket/15310#comment:6
https://trac.sagemath.org/ticket/15310#comment:6
<ul>
<li><strong>commit</strong>
changed from <em>7487b62fe657ef04722f06fa5c1e7647855e4f89</em> to <em>6abda3c9eb7fedd8b63ad135a9b04f6469ae570d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6abda3c9eb7fedd8b63ad135a9b04f6469ae570d"><span class="icon"></span>6abda3c</a></td><td><code>trac #15310: Wilson's construction of Transversal Designs</code>
</td></tr></table>
TicketncohenThu, 03 Apr 2014 14:32:13 GMT
https://trac.sagemath.org/ticket/15310#comment:7
https://trac.sagemath.org/ticket/15310#comment:7
<p>
Rebased (and ready for a review <code>:-P</code>)
</p>
<p>
Nathann
</p>
TicketncohenFri, 04 Apr 2014 09:43:00 GMTcc set
https://trac.sagemath.org/ticket/15310#comment:8
https://trac.sagemath.org/ticket/15310#comment:8
<ul>
<li><strong>cc</strong>
<em>wdj</em> <em>rbeezer</em> <em>brett</em> <em>dimpase</em> added
</li>
</ul>
TicketgitFri, 04 Apr 2014 09:43:30 GMTcommit changed
https://trac.sagemath.org/ticket/15310#comment:9
https://trac.sagemath.org/ticket/15310#comment:9
<ul>
<li><strong>commit</strong>
changed from <em>6abda3c9eb7fedd8b63ad135a9b04f6469ae570d</em> to <em>effb0ac5dc265553a6c4fb7ce9a1337262f4d549</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=effb0ac5dc265553a6c4fb7ce9a1337262f4d549"><span class="icon"></span>effb0ac</a></td><td><code>trac #15310: Wilson's construction of Transversal Designs</code>
</td></tr></table>
TicketgitSun, 06 Apr 2014 07:52:28 GMTcommit changed
https://trac.sagemath.org/ticket/15310#comment:10
https://trac.sagemath.org/ticket/15310#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>effb0ac5dc265553a6c4fb7ce9a1337262f4d549</em> to <em>03f896c363e23a00fabf0b38b87a277354f07327</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=03f896c363e23a00fabf0b38b87a277354f07327"><span class="icon"></span>03f896c</a></td><td><code>trac #15310: Wilson's construction of Transversal Designs</code>
</td></tr></table>
TicketncohenTue, 08 Apr 2014 09:45:43 GMTcc, dependencies changed
https://trac.sagemath.org/ticket/15310#comment:11
https://trac.sagemath.org/ticket/15310#comment:11
<ul>
<li><strong>cc</strong>
<em>vdelecroix</em> added
</li>
<li><strong>dependencies</strong>
changed from <em>#15287</em> to <em>#15287, #15431</em>
</li>
</ul>
TicketgitTue, 08 Apr 2014 09:45:54 GMTcommit changed
https://trac.sagemath.org/ticket/15310#comment:12
https://trac.sagemath.org/ticket/15310#comment:12
<ul>
<li><strong>commit</strong>
changed from <em>03f896c363e23a00fabf0b38b87a277354f07327</em> to <em>6357236d82dd6714eb59a7e63bb22a7f02c18e88</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=79ea5026dc218290dc0944ecebdcabd35555cbb1"><span class="icon"></span>79ea502</a></td><td><code>trac #15431: depends on #15287</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ec6c09e9bc37693f5602b464dbc8b0224d4d5b46"><span class="icon"></span>ec6c09e</a></td><td><code>trac #15431: depends on #15368</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6fbef0c97f1c88dd9c0ace0cf1a1d67852fd3304"><span class="icon"></span>6fbef0c</a></td><td><code>trac #15431 : Construction of TD(6,12)</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c87cac5f35036a820f877ab891eb35cffa1784a1"><span class="icon"></span>c87cac5</a></td><td><code>trac #15431: rebase on updated #15287</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ba232b6494858c8991ffdcaf12ce172dfbb18de0"><span class="icon"></span>ba232b6</a></td><td><code>trac #15431: rebase on 6.2.beta6</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a02aa52e638e571525099c88537571bac5362e61"><span class="icon"></span>a02aa52</a></td><td><code>trac #15431: Reviewer's remarks</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=4adf6b5792919daea356c66d511fc621776d0a77"><span class="icon"></span>4adf6b5</a></td><td><code>trac #15431: Reviewer's remark II</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=47ffd9153b474fbf2b4f560e726b0cfdbcb0af53"><span class="icon"></span>47ffd91</a></td><td><code>trac #15431: remove old todo</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=a537755ebc4522efd30c12c9225abfcac1d36a90"><span class="icon"></span>a537755</a></td><td><code>trac #15431: Back to the standard definition of TD</code>
</td></tr><tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6357236d82dd6714eb59a7e63bb22a7f02c18e88"><span class="icon"></span>6357236</a></td><td><code>trac #15310: Rebase on updated #15431</code>
</td></tr></table>
TicketgitThu, 24 Apr 2014 10:08:02 GMTcommit changed
https://trac.sagemath.org/ticket/15310#comment:13
https://trac.sagemath.org/ticket/15310#comment:13
<ul>
<li><strong>commit</strong>
changed from <em>6357236d82dd6714eb59a7e63bb22a7f02c18e88</em> to <em>25f5959ec5fe7ccd1479fdbdcd489cf550933c7e</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=25f5959ec5fe7ccd1479fdbdcd489cf550933c7e"><span class="icon"></span>25f5959</a></td><td><code>trac #15310: Merged into 6.2.rc0</code>
</td></tr></table>
TicketgitThu, 24 Apr 2014 14:12:48 GMTcommit changed
https://trac.sagemath.org/ticket/15310#comment:14
https://trac.sagemath.org/ticket/15310#comment:14
<ul>
<li><strong>commit</strong>
changed from <em>25f5959ec5fe7ccd1479fdbdcd489cf550933c7e</em> to <em>f23fa885ee5a080f2a8051f23f7fc9f130541849</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f23fa885ee5a080f2a8051f23f7fc9f130541849"><span class="icon"></span>f23fa88</a></td><td><code>trac #15310: useless checks</code>
</td></tr></table>
TicketvdelecroixSun, 27 Apr 2014 17:53:05 GMT
https://trac.sagemath.org/ticket/15310#comment:15
https://trac.sagemath.org/ticket/15310#comment:15
<p>
Hi Nathann,
</p>
<p>
I am not sure I would be able to do the full review. Nevertheless, you can can speed up <strong>a lot</strong> the function <code>find_wilson_decomposition</code> using the fact that if a TD(k,n) exists then we have the inequality <code>k <= n+1</code>. Here is a sample version of what can be done:
</p>
<pre class="wiki">def find_wilson_decomposition(k,n):
# we can start from k-1 since we need a TD(k+1,t)
for t in range(max(1,k-1),n-1):
u = n%t
# We ensure that 1<=u and
# u <= k-2 since we need a TD(k,u)
if u == 0 or u <= k-2:
continue
m = n//t
# k < m+2 since we need a TD(k,m)
if k >= m+2:
break
if (transversal_design(k ,m , availability=True) and
transversal_design(k ,m+1, availability=True) and
transversal_design(k+1,t , availability=True) and
transversal_design(k ,u , availability=True)):
return k,m,t,u
return False
</pre><p>
You can check that there is no stupid call to <code>find_wilson_decomposition</code> with the following
</p>
<pre class="wiki">sage: from sage.combinat.designs.orthogonal_arrays import find_wilson_decomposition
sage: find_wilson_decomposition(7,71)
(7, 8, 8, 7)
sage: find_wilson_decomposition.get_cache() # get the list of cached values
...
</pre>
TicketncohenSun, 27 Apr 2014 18:01:07 GMT
https://trac.sagemath.org/ticket/15310#comment:16
https://trac.sagemath.org/ticket/15310#comment:16
<p>
Yoooooooooooo !!
</p>
<blockquote class="citation">
<p>
I am not sure I would be able to do the full review.
</p>
</blockquote>
<p>
PLeaaaaaaaaaaase.. I swear, all the results are checked before being returned ! And the algorithms are so weird that the slightest typo would make all results wrong <code>:-P</code>
</p>
<blockquote class="citation">
<p>
Nevertheless, you can can speed up <strong>a lot</strong> the function <code>find_wilson_decomposition</code> using the fact that if a TD(k,n) exists then we have the inequality <code>k <= n+1</code>.
</p>
</blockquote>
<p>
Oh ?
</p>
<blockquote class="citation">
<p>
Here is a sample version of what can be done:
</p>
</blockquote>
<p>
What does it change exactly ? That the <code>TD(k,u)</code> is not called when the answer is obviously no ? Wouldn't we get the very same result by moving the check of <code>TD(k,u)</code> to the top of the 4 tests ?
</p>
<p>
Nathann
</p>
TicketncohenSun, 27 Apr 2014 18:05:07 GMT
https://trac.sagemath.org/ticket/15310#comment:17
https://trac.sagemath.org/ticket/15310#comment:17
<p>
Yeah, you are right, let's add those tests before the big if. I will do it in a second.
</p>
<p>
Nathann
</p>
TicketncohenSun, 27 Apr 2014 18:16:10 GMT
https://trac.sagemath.org/ticket/15310#comment:18
https://trac.sagemath.org/ticket/15310#comment:18
<p>
What about this ?
</p>
<pre class="wiki"> if ( k < m+2 and k < t+3 and k < u+2 and
transversal_design(k ,m , availability=True) and
transversal_design(k ,m+1, availability=True) and
transversal_design(k+1,t , availability=True) and
transversal_design(k ,u , availability=True)):
return k,m,t,u
</pre>
TicketncohenSun, 27 Apr 2014 18:23:32 GMT
https://trac.sagemath.org/ticket/15310#comment:19
https://trac.sagemath.org/ticket/15310#comment:19
<p>
Oh I see, you tested all of them by changing the bounds of the loops. Right. I'll change that.
</p>
<p>
Nathann
</p>
TicketncohenSun, 27 Apr 2014 18:39:07 GMT
https://trac.sagemath.org/ticket/15310#comment:20
https://trac.sagemath.org/ticket/15310#comment:20
<p>
Why isn't it <code>for t in range(max(1,k),n-1):</code> in the first loop ?
</p>
TicketgitSun, 27 Apr 2014 18:49:24 GMTcommit changed
https://trac.sagemath.org/ticket/15310#comment:21
https://trac.sagemath.org/ticket/15310#comment:21
<ul>
<li><strong>commit</strong>
changed from <em>f23fa885ee5a080f2a8051f23f7fc9f130541849</em> to <em>62f0158c281c55523a532d5ef21c666ba9c7dc3d</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=62f0158c281c55523a532d5ef21c666ba9c7dc3d"><span class="icon"></span>62f0158</a></td><td><code>trac #15310: cutting some branches of the exploration</code>
</td></tr></table>
TicketvdelecroixSun, 27 Apr 2014 18:52:15 GMT
https://trac.sagemath.org/ticket/15310#comment:22
https://trac.sagemath.org/ticket/15310#comment:22
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15310#comment:20" title="Comment 20">ncohen</a>:
</p>
<blockquote class="citation">
<p>
Why isn't it <code>for t in range(max(1,k),n-1):</code> in the first loop ?
</p>
</blockquote>
<p>
My mistake. This is why I did not write a branch for that... I wanted you to check carefully!!
</p>
TicketncohenSun, 27 Apr 2014 18:52:50 GMT
https://trac.sagemath.org/ticket/15310#comment:23
https://trac.sagemath.org/ticket/15310#comment:23
<p>
Well, in this direction it is not a problem <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketvdelecroixWed, 30 Apr 2014 13:34:00 GMT
https://trac.sagemath.org/ticket/15310#comment:24
https://trac.sagemath.org/ticket/15310#comment:24
<p>
Hi Nathann,
</p>
<p>
Brett Stevens is in sabatical in Bordeaux and explains me in full details the Wilson construction. Good news: I have enough background to starts seriously the review.
</p>
<p>
1) There is a much simpler construction than the Wilson one, often called the Kronecker product, which from a TD(k,t) and a TD(k,n) builds a TD(k,nt) (this is basically the case u=0 in Wilson construction). We found that Wilson construction does not apply to a TD(3,6) but the Kronecker product does! Do you prefer opening a new ticket or including it in this one?
</p>
<p>
2) The programming design with TD calling OA is very bad. In OA there is a nice <code>EmptySetError</code> which has an important mathematical meaning. But if you ask for a transversal design you get instead a <code>NotImplementedError</code> which is much less informative
</p>
<pre class="wiki">sage: designs.orthogonal_array(6,3) # this is great
Traceback (most recent call last)
...
EmptySetError: No Orthogonal Array exists when k>=n+t
sage: designs.transversal_design(6,3) # this is bad
Traceback (most recent call last)
...
NotImplementedError: I don't know how to build this Transversal Design!
</pre><p>
In the ideal world, Sage would only return a design or raise an <code>EmptySetError</code> with a meaningful message mentionning a theorem. And I learned from Brett that there exist several situations where we know mathematically that a TD(k,n) does not exist. When <code>availability=True</code> it would be nice to get a troolean: True (means yes), False (means no), Unknown in <code>sage.misc.unknown</code> (means I do not know). And then, you might change the name <code>availability</code> to <code>existence</code>.
</p>
<p>
3) The loop where you test the Wilson construction is 2.86 seconds on my (dual core) computer. I am not sure it deserves a <code># long time</code>.
</p>
<p>
4) Could you mention the following reference as a todo
</p>
<ul><li>AUTHOR = Colbourn, Charles J. and Dinitz, Jeffrey H.
</li><li>TITLE = Making the MOLS table
</li><li>BOOKTITLE = Computational and constructive design theory
</li><li>SERIES = Math. Appl.
</li><li>VOLUME = 368
</li><li>PAGES = 67--134
</li><li>PUBLISHER = Kluwer Acad. Publ., Dordrecht
</li><li>YEAR = 1996
</li></ul><p>
They have a slightly improved Wilson construction for u=1, 2 that requires less material (ie not four full smaller TDs)... and hence gives more cases where the construction applies.
</p>
<p>
Cheers,
Vincent
</p>
TicketncohenWed, 30 Apr 2014 13:44:46 GMT
https://trac.sagemath.org/ticket/15310#comment:25
https://trac.sagemath.org/ticket/15310#comment:25
<p>
Yo !
</p>
<blockquote class="citation">
<p>
Brett Stevens is in sabatical in Bordeaux and explains me in full details the Wilson construction. Good news: I have enough background to starts seriously the review.
</p>
</blockquote>
<p>
Ahahaha. Well you must have more background that I have then, I am jealous <code>:-P</code>
</p>
<blockquote class="citation">
<p>
1) There is a much simpler construction than the Wilson one, often called the Kronecker product, which from a TD(k,t) and a TD(k,n) builds a TD(k,nt) (this is basically the case u=0 in Wilson construction). We found that Wilson construction does not apply to a TD(3,6) but the Kronecker product does! Do you prefer opening a new ticket or including it in this one?
</p>
</blockquote>
<p>
I would say open a new ticket because this ticket does not only implement Wilson's construction, it also adds some "availability" flags to constructors and thus this ticket is a dependency for several others. Hence if we implement it in another ticket the other ones can be reviewed in the meantime.
</p>
<p>
I also got word from Julian Abel that the Wilson Decomposition I implemented was not the best one, and that some variants may be useful. I copy/paste what he told me here (he probably will not mind)
</p>
<pre class="wiki">I note from your list of known MOLS that you've used Wilson's theorem with 1 truncated group, but not more. The next most important variants are
where there are (1) 2 truncated groups (2) 1 spike block or 1 truncated group and a spike. These variants are as follows:
Theorem 1: If there are k+2 MOLS(t), and k MOLS(s) for s=g, g+1, g+2, u_1, u_2, where 0 \leq u_1, u_2 \leq t, then there are k MOLS(gt + u_1 + u_2).
Theorem 2: If there are k+x MOLS(t), and k MOLS(s) for s=g, g+1, g+x, g+x, where 0 \leq u_1, u_2 \leq t, x> 0 then there are k MOLS(gt + x).
Theorem 3: If there are k+x+1 MOLS(t), and k MOLS(s) for s=g, g+1, g+2, g+x, u_1, where 0 \ leq u_1 \leq t, x > 0, then there are k MOLS(gt + x + u_1).
For instance, Th. 1 gives 6 MOLS for v=106 = 7. 13 + 7 + 8. Theorem 2 gives 7 MOLS(v) for v=155 = 8.19 + 3. And Theorem 3 gives 6 MOLS(v) for v=148= 7.19 + 6 + 9.
</pre><p>
He also pointed me toward references where I can read those constructions, but I have not begun this step yet and he told me it would be hard to read. Still, it has to be done.
</p>
<blockquote class="citation">
<p>
2) The programming design with TD calling OA is very bad. In OA there is a nice <code>EmptySetError</code> which has an important mathematical meaning. But if you ask for a transversal design you get instead a <code>NotImplementedError</code> which is much less informative
</p>
</blockquote>
<p>
How is that a result of TD calling OA ?
</p>
<blockquote class="citation">
<p>
In the ideal world, Sage would only return a design or raise an <code>EmptySetError</code> with a meaningful message mentionning a theorem. And I learned from Brett that there exist several situations where we know mathematically that a TD(k,n) does not exist. When <code>availability=True</code> it would be nice to get a troolean: True (means yes), False (means no), Unknown in <code>sage.misc.unknown</code> (means I do not know).
</p>
</blockquote>
<p>
Well. No problem if "if Unknown" is equivalent to "if False".
</p>
<blockquote class="citation">
<p>
And then, you might change the name <code>availability</code> to <code>existence</code>.
</p>
</blockquote>
<p>
Could we do that on top of <a class="closed ticket" href="https://trac.sagemath.org/ticket/12267" title="defect: multiply defined labels when using sagetex with multline (closed: fixed)">#12267</a> ? I would prefer those patches to be merged like that, and then we can update stuff. Otherwise it means fixing many conflicts with the stuff above, but I agree that it is a good idea.
</p>
<blockquote class="citation">
<p>
3) The loop where you test the Wilson construction is 2.86 seconds on my (dual core) computer. I am not sure it deserves a <code># long time</code>.
</p>
</blockquote>
<p>
Well, I usually set <code>#long </code> even for 2 seconds. Most tests are faster than that, andyou can have many "2 seconds" tests. I don't mind adding/removing flags like that, but you can also add a commit if you like.
</p>
<blockquote class="citation">
<p>
4) Could you mention the following reference as a todo
</p>
<ul><li>AUTHOR = Colbourn, Charles J. and Dinitz, Jeffrey H.
</li><li>TITLE = Making the MOLS table
</li><li>BOOKTITLE = Computational and constructive design theory
</li><li>SERIES = Math. Appl.
</li><li>VOLUME = 368
</li><li>PAGES = 67--134
</li><li>PUBLISHER = Kluwer Acad. Publ., Dordrecht
</li><li>YEAR = 1996
</li></ul><p>
They have a slightly improved Wilson construction for u=1, 2 that requires less material (ie not four full smaller TDs)... and hence gives more cases where the construction applies.
</p>
</blockquote>
<p>
okayokay, good idea ! I will add a commit in a second.
</p>
<p>
Nathann
</p>
TicketgitWed, 30 Apr 2014 13:56:07 GMTcommit changed
https://trac.sagemath.org/ticket/15310#comment:26
https://trac.sagemath.org/ticket/15310#comment:26
<ul>
<li><strong>commit</strong>
changed from <em>62f0158c281c55523a532d5ef21c666ba9c7dc3d</em> to <em>d74341411288315f13da3d4383e515b884ba7440</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=d74341411288315f13da3d4383e515b884ba7440"><span class="icon"></span>d743414</a></td><td><code>trac #15310: reviewer's remarks</code>
</td></tr></table>
TicketvdelecroixWed, 30 Apr 2014 13:58:50 GMT
https://trac.sagemath.org/ticket/15310#comment:27
https://trac.sagemath.org/ticket/15310#comment:27
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15310#comment:25" title="Comment 25">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
1) There is a much simpler construction than the Wilson one, often called the Kronecker product, which from a TD(k,t) and a TD(k,n) builds a TD(k,nt) (this is basically the case u=0 in Wilson construction). We found that Wilson construction does not apply to a TD(3,6) but the Kronecker product does! Do you prefer opening a new ticket or including it in this one?
</p>
</blockquote>
<p>
I would say open a new ticket because this ticket does not only implement Wilson's construction, it also adds some "availability" flags to constructors and thus this ticket is a dependency for several others. Hence if we implement it in another ticket the other ones can be reviewed in the meantime.
</p>
</blockquote>
<p>
Actually, the product construction is what you are doing in <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a>. You can see it as a particular case of Wilson construction.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
2) The programming design with TD calling OA is very bad. In OA there is a nice <code>EmptySetError</code> which has an important mathematical meaning. But if you ask for a transversal design you get instead a <code>NotImplementedError</code> which is much less informative
</p>
</blockquote>
<p>
How is that a result of TD calling OA ?
</p>
</blockquote>
<p>
I would better say not calling OA appropriately. line 79
</p>
<pre class="wiki"> elif orthogonal_array(k,n, check = False, availability = True):
...
</pre><p>
I still found that having half of the implementation in TD and half of the implementation in OA is very confusing.
</p>
<blockquote class="citation">
<p>
Well. No problem if "if Unknown" is equivalent to "if False".
</p>
</blockquote>
<p>
It is. You do not know your troolean algebra !?
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
And then, you might change the name <code>availability</code> to <code>existence</code>.
</p>
</blockquote>
<p>
Could we do that on top of <a class="closed ticket" href="https://trac.sagemath.org/ticket/12267" title="defect: multiply defined labels when using sagetex with multline (closed: fixed)">#12267</a> ? I would prefer those patches to be merged like that, and then we can update stuff. Otherwise it means fixing many conflicts with the stuff above, but I agree that it is a good idea.
</p>
</blockquote>
<p>
Make sense. I will open a ticket for that.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
3) The loop where you test the Wilson construction is 2.86 seconds on my (dual core) computer. I am not sure it deserves a <code># long time</code>.
</p>
</blockquote>
<p>
Well, I usually set <code>#long </code> even for 2 seconds. Most tests are faster than that, andyou can have many "2 seconds" tests. I don't mind adding/removing flags like that, but you can also add a commit if you like.
</p>
</blockquote>
<p>
No do not worry about this.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
4) Could you mention the following reference as a todo
</p>
<ul><li>AUTHOR = Colbourn, Charles J. and Dinitz, Jeffrey H.
</li><li>TITLE = Making the MOLS table
</li><li>BOOKTITLE = Computational and constructive design theory
</li><li>SERIES = Math. Appl.
</li><li>VOLUME = 368
</li><li>PAGES = 67--134
</li><li>PUBLISHER = Kluwer Acad. Publ., Dordrecht
</li><li>YEAR = 1996
</li></ul><p>
They have a slightly improved Wilson construction for u=1, 2 that requires less material (ie not four full smaller TDs)... and hence gives more cases where the construction applies.
</p>
</blockquote>
<p>
okayokay, good idea ! I will add a commit in a second.
</p>
</blockquote>
<p>
and please, add also the references you got from Julian Abel. I guess that they are pretty similar.
</p>
<p>
Vincent
</p>
TicketncohenWed, 30 Apr 2014 14:07:31 GMT
https://trac.sagemath.org/ticket/15310#comment:28
https://trac.sagemath.org/ticket/15310#comment:28
<p>
Yo !
</p>
<blockquote class="citation">
<p>
Actually, the product construction is what you are doing in <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a>. You can see it as a particular case of Wilson construction.
</p>
</blockquote>
<p>
Oh. Cool, then. Must prove I am on the right path <code>:-D</code>
</p>
<blockquote class="citation">
<p>
I would better say not calling OA appropriately. line 79
</p>
<pre class="wiki"> elif orthogonal_array(k,n, check = False, availability = True):
...
</pre></blockquote>
<p>
Oh. And you want to transfer the "False" answer which means "that stuff does not exist" as an exception ? Then do you mind if we do that in the ticket which will change "availability" to "existence" ? It would be easier to not fix many conflicts in many patches. But it is a good idea and it will be implemented, be sure I don't say this because I don't want to do it. It *is* a good idea.
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Well. No problem if "if Unknown" is equivalent to "if False".
</p>
</blockquote>
<p>
It is. You do not know your troolean algebra !?
</p>
</blockquote>
<p>
To me it should raise an Exception. You just cannot trust these things to do what they should.
</p>
<blockquote class="citation">
<p>
Make sense. I will open a ticket for that.
</p>
</blockquote>
<p>
Thanks. Add me in Cc when you do, of course <code>:-)</code>
</p>
<blockquote class="citation">
<p>
No do not worry about this.
</p>
</blockquote>
<p>
Too late <code>:-P</code>
</p>
<blockquote class="citation">
<p>
and please, add also the references you got from Julian Abel. I guess that they are pretty similar.
</p>
</blockquote>
<p>
Hmmm... Not now please, I will probably have more questions to ask him and right now we are exchanging email about a construction of MOLS that I cannot reproduce. I implemented quite a lot of specific constructions of MOLS/OA during the last days. Besides <a class="closed ticket" href="https://trac.sagemath.org/ticket/16241" title="enhancement: New MOLS shared by Ian Wanless (closed: fixed)">#16241</a> <a class="closed ticket" href="https://trac.sagemath.org/ticket/16236" title="enhancement: Five mutually orthogonal latin squares of order 12 (closed: fixed)">#16236</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/16235" title="enhancement: A pair of orthogonal latin squares of order 10 (closed: fixed)">#16235</a> I have the following ready :
</p>
<pre class="wiki">~$ grep "^def " qd.py
def OA_from_quasi_difference_matrix(M,G,add_col=True):
def OA_from_wider_OA(OA,k):
def OA_6_20(k,n,availability=False):
def OA_7_21(k,n,availability=False):
def OA_5_22(k,n,availability=False):
def OA_7_60(k,n,availability=False):
def OA_9_24(k,n,availability=False):
def OA_6_26(k,n,availability=False):
def OA_7_28(k,n,availability=False):
def OA_6_30(k,n,availability=False):
def OA_7_33(k,n,availability=False):
def OA_6_34(k,n,availability=False):
def OA_7_35(k,n,availability=False):
def OA_10_36(k,n,availability=False):
def OA_6_38(k,n,availability=False):
def OA_7_39(k,n,availability=False):
def OA_9_40(k,n,availability=False):
def OA_10_48(k,n,availability=False):
def OA_9_40b(k,n,availability=False):
</pre><p>
Well. Except the last 3. Those are the ones we are fighting against at the moment <code>:-)</code>
</p>
<p>
Nathann
</p>
TicketbrettWed, 30 Apr 2014 14:36:52 GMT
https://trac.sagemath.org/ticket/15310#comment:29
https://trac.sagemath.org/ticket/15310#comment:29
<p>
I will jump in here. Julian Able's other versions of Wilson's construction are the ones discussed in the Colbourn and Dinitz reference. I was wrong about the details when I chatted with Vincent: I said they simplified when $u$ was a nice value, but your posted email from Julian reminds me that these are multiple truncations. I do not think these need to go into a first round. I would advocate getting the basic Wilson's theorem into the official Sage release and then adding more intricate variations
</p>
<p>
With regards to the product construction, I think that when Wilson's construction is passed $u=0$ then it should not check that TD$(k+1,t)$, TD$(k,u)$, TD$(k,m+1)$ exist at all. It should check that TD(k,t)$ and $TD(k,m)$ exist and call the product construction. Then in your find_wilson_decomposition you should also include $u=0$ in the search loops
</p>
<p>
I am waiting for sage to compile, then I will get the new commit and look more closely at the code.
</p>
<p>
Here are some additional thoughts that apply to the whole TD/OA enterprise rather than just this patch (If I should be discussing these things somewhere else because they are more general comments then please let me know and point me to where to have this discussion)
</p>
<ul><li>(anticipating ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/16231" title="enhancement: Equivalence between OA/TD/MOLS (closed: fixed)">#16231</a>) the OA/TD/MOLS object should have a single internal format and then constructor operations to output other equivalent objects. I think OA is the most general since it can have arbitrary $t$ (Which TD does not) and arbitrary $\lambda$ (which MOLS cannot have), etc. I think all internal operations should be done on OAs; that is all constructions are as OAs. Then the object should be able to output a TD or MOLS as alternatives. The user should be able to call for whichever object they want but this would be just a case now of doing a sanity check (make sure $t=2$ of they asked for TD), translate the parameters to OA parameters, find the object if possible, and translate it into the desired output format. This single internal format would eliminate the possibility of methods eventually trying to call themselves again. But the users will get the experience they expect with each type of object.
</li></ul><ul><li>There are number of known parameters which cannot exist. The Bruck Ryser Chowla Theorm gives the non-existence of many TD(n+1,n). Additionally C. Lam proved that TD(11,10) cannot exist. Finally there is some work that shows that if $k$ is large enough then the existence of TD$(k,n)$ implies the existence of TD$(n+1,n)$ and so the non-existence results can percolate downwards in $k$. I do not think we should have all of the known results in this change. We should only implement the easy ones or possibly none at all at first
</li></ul>
TicketvdelecroixWed, 30 Apr 2014 14:46:10 GMT
https://trac.sagemath.org/ticket/15310#comment:30
https://trac.sagemath.org/ticket/15310#comment:30
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15310#comment:29" title="Comment 29">brett</a>:
</p>
<blockquote class="citation">
<p>
With regards to the product construction, I think that when Wilson's construction is passed $u=0$ then it should not check that TD$(k+1,t)$, TD$(k,u)$, TD$(k,m+1)$ exist at all. It should check that TD(k,t)$ and $TD(k,m)$ exist and call the product construction. Then in your find_wilson_decomposition you should also include $u=0$ in the search loops
</p>
</blockquote>
<p>
Yes. It is possible to have that in <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a>: we can replace the two functions with one. But I am not sure it would be faster/clearer.
</p>
<blockquote class="citation">
<ul><li>(anticipating ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/16231" title="enhancement: Equivalence between OA/TD/MOLS (closed: fixed)">#16231</a>) the OA/TD/MOLS object should have a single internal format and then constructor operations to output other equivalent objects. I think OA is the most general since it can have arbitrary $t$ (Which TD does not) and arbitrary $\lambda$ (which MOLS cannot have), etc. I think all internal operations should be done on OAs; that is all constructions are as OAs. Then the object should be able to output a TD or MOLS as alternatives. The user should be able to call for whichever object they want but this would be just a case now of doing a sanity check (make sure $t=2$ of they asked for TD), translate the parameters to OA parameters, find the object if possible, and translate it into the desired output format. This single internal format would eliminate the possibility of methods eventually trying to call themselves again. But the users will get the experience they expect with each type of object.
</li></ul></blockquote>
<p>
This is an important issue I started to discuss with Nathann in <a class="closed ticket" href="https://trac.sagemath.org/ticket/15431" title="enhancement: Transversal Design TD(6,12) (closed: fixed)">#15431</a>... and I am in favour of implementing all the code with OA conventions.
</p>
<blockquote class="citation">
<ul><li>There are number of known parameters which cannot exist. The Bruck Ryser Chowla Theorm gives the non-existence of many TD(n+1,n). Additionally C. Lam proved that TD(11,10) cannot exist. Finally there is some work that shows that if $k$ is large enough then the existence of TD$(k,n)$ implies the existence of TD$(n+1,n)$ and so the non-existence results can percolate downwards in $k$. I do not think we should have all of the known results in this change. We should only implement the easy ones or possibly none at all at first
</li></ul></blockquote>
<p>
Cool: look at ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/16272" title="enhancement: redesign transversal designs (closed: fixed)">#16272</a>. I will add those references to the description. If you have other non-existence theorems please post them on <a class="closed ticket" href="https://trac.sagemath.org/ticket/16272" title="enhancement: redesign transversal designs (closed: fixed)">#16272</a>.
</p>
TicketncohenWed, 30 Apr 2014 18:04:23 GMT
https://trac.sagemath.org/ticket/15310#comment:31
https://trac.sagemath.org/ticket/15310#comment:31
<p>
Yo !
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
With regards to the product construction, I think that when Wilson's construction is passed $u=0$ then it should not check that TD$(k+1,t)$, TD$(k,u)$, TD$(k,m+1)$ exist at all. It should check that TD(k,t)$ and $TD(k,m)$ exist and call the product construction. Then in your find_wilson_decomposition you should also include $u=0$ in the search loops
</p>
</blockquote>
</blockquote>
<p>
I implemented it this way because I followed Douglas Stinson's book, which defines this construction explicitly for 1<=u.
</p>
<blockquote class="citation">
<p>
This is an important issue I started to discuss with Nathann in <a class="closed ticket" href="https://trac.sagemath.org/ticket/15431" title="enhancement: Transversal Design TD(6,12) (closed: fixed)">#15431</a>... and I am in favour of implementing all the code with OA conventions.
</p>
</blockquote>
<p>
I hate useless abstraction. Look, for the moment there is some code left in the constructor of MOLS but it will be removed soon, by the TD construction. I am against forcing .... myself .... to translate every construction of MOLS/TD into OA, because implementing code like that is extremely tricky. I just spent two full days (no joke) because I misunderstood one line of a construction, and I was helped by the guy who actually first wrote it. I implemented code like <a class="closed ticket" href="https://trac.sagemath.org/ticket/14562" title="enhancement: Steiner Quadruple Systems (closed: fixed)">#14562</a> and you wouldn't believe the number of times I was convinced that the construction was wrong. Look at the code, really. There is one line among those at which I stared for 30 solid minutes. Only this line, nothing else. That's no joke, and having to translate constructions from unclear papers can mean a lot of headaches while you debug.
</p>
<p>
Anyway, right now I don't think that it is really a problem... There is a lot of work needing to be done, and this work is implementing constructions, any kind of constructions, in any formalism you like. We can merge everything later if we need. But really what we need right now are constructions, and nothing else.
</p>
<blockquote class="citation">
<p>
Cool: look at ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/16272" title="enhancement: redesign transversal designs (closed: fixed)">#16272</a>. I will add those references to the description. If you have other non-existence theorems please post them on <a class="closed ticket" href="https://trac.sagemath.org/ticket/16272" title="enhancement: redesign transversal designs (closed: fixed)">#16272</a>.
</p>
</blockquote>
<p>
Yep, non-existence results are good and the Unknown truth value really helps here. We could also implement something funny : if a guy ever needs to say in a paper that "this design exists", we could have Sage return some information on the path used by the constructions.
</p>
<p>
I mean. We can say where the basic constructions come from (we have the references), and we can also say how the recursive constructions are applied. Sooooo what we have is a way to say that this design can be obtained by applying this or that constructions in this way,using the following elementary blocks whose existence has been proved there and there. Really, we can do that <code>:-)</code>
</p>
<p>
But that's nice things for later. What we need to do is beat the Handbook's MOLS table while providing the actual MOLS. That would be something we could boast about <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketncohenWed, 30 Apr 2014 18:08:54 GMT
https://trac.sagemath.org/ticket/15310#comment:32
https://trac.sagemath.org/ticket/15310#comment:32
<p>
By the way, all designs constructions in the list I gave above now work. I will implement some more before sending the patch, but they do work. Plus I will need stuff like <a class="closed ticket" href="https://trac.sagemath.org/ticket/16261" title="enhancement: Default behaviour of AdditiveAbelianGroup(a_tuple) (closed: fixed)">#16261</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/16269" title="enhancement: Cartesian Products of additive groups (closed: fixed)">#16269</a> before.
</p>
TicketncohenWed, 30 Apr 2014 18:14:53 GMT
https://trac.sagemath.org/ticket/15310#comment:33
https://trac.sagemath.org/ticket/15310#comment:33
<p>
By the way will you be in Bordeaux during <a class="missing wiki">July/August?</a> ? I have no plans yet <code>:-D</code>
</p>
<p>
Nathann
</p>
TicketvdelecroixWed, 30 Apr 2014 19:12:25 GMT
https://trac.sagemath.org/ticket/15310#comment:34
https://trac.sagemath.org/ticket/15310#comment:34
<p>
Hello,
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15310#comment:31" title="Comment 31">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
This is an important issue I started to discuss with Nathann in <a class="closed ticket" href="https://trac.sagemath.org/ticket/15431" title="enhancement: Transversal Design TD(6,12) (closed: fixed)">#15431</a>... and I am in favour of implementing all the code with OA conventions.
</p>
</blockquote>
<p>
I hate useless abstraction. Look, for the moment there is some code left in the constructor of MOLS but it will be removed soon, by the TD construction. I am against forcing .... myself .... to translate every construction of MOLS/TD into OA, because implementing code like that is extremely tricky. I just spent two full days (no joke) because I misunderstood one line of a construction, and I was helped by the guy who actually first wrote it. I implemented code like <a class="closed ticket" href="https://trac.sagemath.org/ticket/14562" title="enhancement: Steiner Quadruple Systems (closed: fixed)">#14562</a> and you wouldn't believe the number of times I was convinced that the construction was wrong. Look at the code, really. There is one line among those at which I stared for 30 solid minutes. Only this line, nothing else. That's no joke, and having to translate constructions from unclear papers can mean a lot of headaches while you debug.
</p>
</blockquote>
<p>
True. But on the other hand
</p>
<ul><li>it is very hard to see what belongs to the OA/TD/MOLS and in few times it will be hard to understand what happens to your input
</li><li>the <code>EmptySetError</code> raised in OA would also makes sense inside the TD. It is better to do trivial check on the input before digging for a construction. So if we want efficient code, we will have to copy paste all sanity checks
</li></ul><blockquote class="citation">
<blockquote class="citation">
<p>
look at ticket <a class="closed ticket" href="https://trac.sagemath.org/ticket/16272" title="enhancement: redesign transversal designs (closed: fixed)">#16272</a>. I will add those references to the description. If you have other non-existence theorems please post them on <a class="closed ticket" href="https://trac.sagemath.org/ticket/16272" title="enhancement: redesign transversal designs (closed: fixed)">#16272</a>.
</p>
</blockquote>
<p>
Yep, non-existence results are good and the Unknown truth value really helps here. We could also implement something funny : if a guy ever needs to say in a paper that "this design exists", we could have Sage return some information on the path used by the constructions.
</p>
<p>
I mean. We can say where the basic constructions come from (we have the references), and we can also say how the recursive constructions are applied. Sooooo what we have is a way to say that this design can be obtained by applying this or that constructions in this way,using the following elementary blocks whose existence has been proved there and there. Really, we can do that <code>:-)</code>
</p>
</blockquote>
<p>
I like it. But I agree that it can be implemented later on.
</p>
<blockquote class="citation">
<p>
But that's nice things for later. What we need to do is beat the Handbook's MOLS table while providing the actual MOLS. That would be something we could boast about <code>:-P</code>
</p>
</blockquote>
<p>
Nice challenge! You want it to be ready for next week?
</p>
TicketncohenWed, 30 Apr 2014 19:18:00 GMT
https://trac.sagemath.org/ticket/15310#comment:35
https://trac.sagemath.org/ticket/15310#comment:35
<p>
Yo !
</p>
<blockquote class="citation">
<p>
True. But on the other hand
</p>
<ul><li>it is very hard to see what belongs to the OA/TD/MOLS and in few times it will be hard to understand what happens to your input
</li></ul></blockquote>
<p>
Well... Just read the constructors of each class, you will see <code>:-P</code>
</p>
<blockquote class="citation">
<ul><li>the <code>EmptySetError</code> raised in OA would also makes sense inside the TD. It is better to do trivial check on the input before digging for a construction. So if we want efficient code, we will have to copy paste all sanity checks
</li></ul></blockquote>
<p>
Yeah, probably ... But that's a very bad reason for changing the data structure <code>:-P</code>
</p>
<blockquote class="citation">
<p>
I like it. But I agree that it can be implemented later on.
</p>
</blockquote>
<p>
Never implement something you don't need. And I am already breaking this rule by implementing designs. I don't have anything to do with designs. I just love them <code>:-P</code>
</p>
<blockquote class="citation">
<p>
Nice challenge! You want it to be ready for next week?
</p>
</blockquote>
<p>
Ahahahahahah. Well, you have some reviews ahead of you, don't you ? <code>:-P</code>
</p>
<p>
Nathann
</p>
TicketbrettThu, 01 May 2014 10:41:11 GMT
https://trac.sagemath.org/ticket/15310#comment:36
https://trac.sagemath.org/ticket/15310#comment:36
<p>
I do not think it is abstraction for abstraction’s sake to have an single internal format. When this gets turned into a class of its own with internal methods, etc. (later, not now) then it will need to have a single internal data structure. For example incidence structures (and by extension, designs) are stored as their sets of sets. The incidence matrix is equivalent but it is not a separate object with its own construction methods distinct from incidence structures. In addition to Vincint's comments, a single internal format allows
</p>
<ul><li>a single place to check all known non-existence results
</li></ul><ul><li>future ease in making this a class
</li></ul><p>
In principle I do not mind if the constructions that you have implemented for TDs stay as they are but are wrapped by OA->TD translation TD construction followed by TD-OA translation. It can be left as a possible future task to clean this up.
</p>
<p>
Some kind of path used to construct an OA/TD is a great idea! This could be really useful to the user. This is used by Charlie Colbourn on his <a class="ext-link" href="http://www.public.asu.edu/~ccolbou/src/tabby/catable.htm"><span class="icon"></span>Covering Array tables</a>, but his cannot be parsed completely to the full list of exact objects and constructions used. I thought a lot about this for CAs in my thesis but I never came up with and format I liked. Are there these kind of certificates for other objects anywhere in Sage that we could look to for ideas?
</p>
<p>
brett
</p>
<p>
p.s. how do I format the link correctly
</p>
TicketvdelecroixThu, 01 May 2014 10:49:57 GMTstatus changed
https://trac.sagemath.org/ticket/15310#comment:37
https://trac.sagemath.org/ticket/15310#comment:37
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Hi,
</p>
<p>
everybody: please, in a given ticket, only discuss the ticket! There is the <a class="ext-link" href="https://groups.google.com/forum/#!forum/sage-devel"><span class="icon"></span>sage-devel</a> mailing lists for discussions. All comments here will typically get lost once it gets merged into Sage... And it might be soon as I set it to positive review.
</p>
<p>
Nathann: you have to rebase <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a> above the last commit in here.
</p>
<p>
Vincent
</p>
TicketncohenThu, 01 May 2014 10:52:35 GMT
https://trac.sagemath.org/ticket/15310#comment:38
https://trac.sagemath.org/ticket/15310#comment:38
<p>
Yo !
</p>
<blockquote class="citation">
<p>
I do not think it is abstraction for abstraction’s sake to have an single internal format. When this gets turned into a class of its own with internal methods, etc. (later, not now) then it will need to have a single internal data structure.
</p>
</blockquote>
<p>
For the moment I did not see the need to turn it into a class. Especially since making it a class will require many useless copies of stuff, each time you ask the class to give you its data or when you build an instance from the data (copy in each direction, for nothing).
</p>
<blockquote class="citation">
<p>
For example incidence structures (and by extension, designs) are stored as their sets of sets.
</p>
</blockquote>
<p>
And I like to work with list of sets indeed <code>:-P</code>
</p>
<blockquote class="citation">
<p>
The incidence matrix is equivalent but it is not a separate object with its own construction methods distinct from incidence structures. In addition to Vincint's comments, a single internal format allows
</p>
<ul><li>a single place to check all known non-existence results
</li></ul><ul><li>future ease in making this a class
</li></ul></blockquote>
<p>
It is true, but if it means that implementing constructions becomes harder, this is too much to pay. Really, give it a try. Today is a holiday, and I have been implementing constructions since I woke up. It is *HARD* and painful.
</p>
<blockquote class="citation">
<p>
Some kind of path used to construct an OA/TD is a great idea! This could be really useful to the user. This is used by Charlie Colbourn on his <a class="ext-link" href="http://www.public.asu.edu/~ccolbou/src/tabby/catable.htm"><span class="icon"></span>http://www.public.asu.edu/~ccolbou/src/tabby/catable.htm</a>Covering Array tables, but his cannot be parsed completely to the full list of exact objects and constructions used. I thought a lot about this for CAs in my thesis but I never came up with and format I liked. Are there these kind of certificates for other objects anywhere in Sage that we could look to for ideas?
</p>
</blockquote>
<p>
I don't think so .... Designs are particularly messy in this respect <code>:-P</code>
</p>
<p>
Nathann
P.S. : Vincent is right, let's discuss this somewhere else. On the otherhand, if you can review this ticket we can use it as a forum afterwards <code>:-D</code>
</p>
TicketncohenThu, 01 May 2014 10:53:34 GMT
https://trac.sagemath.org/ticket/15310#comment:39
https://trac.sagemath.org/ticket/15310#comment:39
<blockquote class="citation">
<p>
everybody: please, in a given ticket, only discuss the ticket! There is the <a class="ext-link" href="https://groups.google.com/forum/#!forum/sage-devel"><span class="icon"></span>sage-devel</a> mailing lists for discussions. All comments here will typically get lost once it gets merged into Sage... And it might be soon as I set it to positive review.
</p>
</blockquote>
<p>
Why are the comments lost ? The ticket still exists long afterwards !
</p>
<blockquote class="citation">
<p>
Nathann: you have to rebase <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a> above the last commit in here.
</p>
</blockquote>
<p>
It creates a conflict ? <code>O_o</code>
</p>
<p>
I thought git would handle this by itself...
</p>
<p>
Nathann
</p>
TicketvdelecroixThu, 01 May 2014 11:05:04 GMT
https://trac.sagemath.org/ticket/15310#comment:40
https://trac.sagemath.org/ticket/15310#comment:40
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15310#comment:39" title="Comment 39">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
everybody: please, in a given ticket, only discuss the ticket! There is the <a class="ext-link" href="https://groups.google.com/forum/#!forum/sage-devel"><span class="icon"></span>sage-devel</a> mailing lists for discussions. All comments here will typically get lost once it gets merged into Sage... And it might be soon as I set it to positive review.
</p>
</blockquote>
<p>
Why are the comments lost ? The ticket still exists long afterwards !
</p>
<blockquote class="citation">
<p>
Nathann: you have to rebase <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a> above the last commit in here.
</p>
</blockquote>
<p>
It creates a conflict ? <code>O_o</code>
</p>
<p>
I thought git would handle this by itself...
</p>
</blockquote>
<p>
git is not god
</p>
<pre class="wiki">Auto-merging src/sage/combinat/designs/orthogonal_arrays.py
CONFLICT (content): Merge conflict in src/sage/combinat/designs/orthogonal_arrays.py
Automatic merge failed; fix conflicts and then commit the result.
</pre>
TicketncohenThu, 01 May 2014 11:13:47 GMT
https://trac.sagemath.org/ticket/15310#comment:41
https://trac.sagemath.org/ticket/15310#comment:41
<blockquote class="citation">
<p>
git is not god
</p>
</blockquote>
<p>
Then we should write a patch to change that.
</p>
<p>
More seriously I thought we had only made unimportant changes since and that it would not conflict. I will update the other one in a second but I will try to finish my constuction first. This one is not reviewed yet already anyway.
</p>
<p>
Nathann
</p>
TicketvdelecroixThu, 01 May 2014 11:24:14 GMTstatus changed
https://trac.sagemath.org/ticket/15310#comment:42
https://trac.sagemath.org/ticket/15310#comment:42
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_review</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15310#comment:41" title="Comment 41">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
git is not god
</p>
</blockquote>
<p>
Then we should write a patch to change that.
</p>
<p>
More seriously I thought we had only made unimportant changes since and that it would not conflict. I will update the other one in a second but I will try to finish my constuction first. This one is not reviewed yet already anyway.
</p>
</blockquote>
<p>
It was! But on the other hand there is a serious issue in <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a>. The function Wilson construction and TD_product should be similar but they are not. Wilson call the <code>transversal_design</code> to start the construction but you have to feed <code>TD_product</code> with the designs! Why is that?
</p>
<p>
I think it would make more sense to merge the two tickets simultaneously. Would you mind if we move the changes you introduced in <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a> in this one (I can even do that by myself).
</p>
TicketncohenThu, 01 May 2014 11:28:28 GMT
https://trac.sagemath.org/ticket/15310#comment:43
https://trac.sagemath.org/ticket/15310#comment:43
<blockquote class="citation">
<p>
It was! But on the other hand there is a serious issue in <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a>.
The function Wilson construction and TD_product should be similar but they are not.
</p>
</blockquote>
<p>
Since when are such things called serious ? <code>:-P</code>
</p>
<p>
Besides I implemented one months after the other, so if you do not mind... :-P
</p>
<blockquote class="citation">
<p>
Wilson call the <code>transversal_design</code> to start the construction but you have to feed <code>TD_product</code> with the designs! Why is that?
</p>
</blockquote>
<p>
Because I suspect that TD_product may be useful to the users later to compute products of their own designs (not the one Sage knows) and I did not think this would happen with wilson decompsition.... If we make TD_product call the designs itself, it makes it less useful, that's all. I saw one as "internal stuff" while the other one could eventually become useful for users.
</p>
<blockquote class="citation">
<p>
I think it would make more sense to merge the two tickets simultaneously.
</p>
</blockquote>
<p>
Why ?
</p>
<blockquote class="citation">
<p>
Would you mind if we move the changes you introduced in <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a> in this one (I can even do that by myself).
</p>
</blockquote>
<p>
Well, stuff is based on the TD ticket, and I will have to deal with the conflicts later if any, so if I can avoid it ....
</p>
<p>
Nathann
</p>
TicketbrettThu, 01 May 2014 13:28:36 GMT
https://trac.sagemath.org/ticket/15310#comment:44
https://trac.sagemath.org/ticket/15310#comment:44
<p>
What if both functions could be called in two ways:
</p>
<p>
1) with just parameters (like Wilson is now) , in which case the program checks if the relevant TD/OAs exist and uses them
</p>
<p>
2) with the relevant TD/OAs passed to the routine (as Product is now), in which case the program checks that they are correct and have the needed parameters and uses them if they are.
</p>
<p>
Python and thus Sage, is good at this kind of flexibility in function calling and in design theory we often want to use specific "ingredients" with property $P$, in a construction and hope/prove that the resulting object had property $P$ as well.
</p>
TicketncohenThu, 01 May 2014 13:36:39 GMT
https://trac.sagemath.org/ticket/15310#comment:45
https://trac.sagemath.org/ticket/15310#comment:45
<p>
Yo !
</p>
<blockquote class="citation">
<p>
1) with just parameters (like Wilson is now) , in which case the program checks if the relevant TD/OAs exist and uses them
</p>
</blockquote>
<p>
This is already done, as Sage will automatically use the product construction to see if such a design exists. When you call <code>designs.orthogonal_array(...)</code> the TD product construction will be called from time to time.
</p>
<blockquote class="citation">
<p>
2) with the relevant TD/OAs passed to the routine (as Product is now), in which case the program checks that they are correct and have the needed parameters and uses them if they are.
</p>
</blockquote>
<p>
Yepyep, we can make the designs be optional parameters indeed ...
</p>
<p>
Really I don't mind but I am writing construction code and there is a lot of work to do. If you want features like that, would you mind implementing them ? It is not a lot of work, you just have to add optional parameters in Wilson's construction equal to None, and if they are set to None Sage will find the designs itself otherwise it will use those that are provided.
</p>
<blockquote class="citation">
<p>
Python and thus Sage, is good at this kind of flexibility in function calling and in design theory we often want to use specific "ingredients" with property $P$, in a construction and hope/prove that the resulting object had property $P$ as well.
</p>
</blockquote>
<p>
Indeed indeed. But it is not like anybody will know that Sage can produce MOLS/OA/TD already, so we have time before the crowd complains about the missing features.. Right now I am just trying to implement what I need to create more TD/OA/MOLS, and we will have all the time in the world to create fancy features when it will be in <code>:-P</code>
</p>
<p>
I am two constructions away from having implemented all explicit construction of length <= 80 that the Handbook provides, but they are tricky ones. Then this step will be done too, and we will have to implement the variants of Wilson's theorem.
</p>
<p>
Nathann
</p>
<p>
Vincent : is there anything I should do on this ticket ?
</p>
TicketvdelecroixThu, 01 May 2014 13:53:08 GMT
https://trac.sagemath.org/ticket/15310#comment:46
https://trac.sagemath.org/ticket/15310#comment:46
<p>
I guess that Brett comment is right. If you focus on constructing more TD/OA/MOLS (which is a fair) you should remove the optional TD arguments from the <code>TD_product</code>. Do not think about other users, they can think by themselves :-P. I will copy/paste that on <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a>.
</p>
<p>
Brett might be the well designed person to implement a nice class to deal with OA. From that we can start having nicer support for product of individual OA.
</p>
<p>
My conclusion is: I think that this ticket is good to go as it is, but I would like that Brett gives his green light.
</p>
TicketncohenThu, 01 May 2014 13:57:58 GMT
https://trac.sagemath.org/ticket/15310#comment:47
https://trac.sagemath.org/ticket/15310#comment:47
<p>
Yo !
</p>
<blockquote class="citation">
<p>
I guess that Brett comment is right. If you focus on constructing more TD/OA/MOLS (which is a fair) you should remove the optional TD arguments from the <code>TD_product</code>. Do not think about other users, they can think by themselves :-P. I will copy/paste that on <a class="closed ticket" href="https://trac.sagemath.org/ticket/16227" title="enhancement: Product construction of Transversal Designs (closed: fixed)">#16227</a>.
</p>
</blockquote>
<p>
Why on earth would you want me to remove features, really ?... If this function is not meant for the users it makes no difference, and if users see it they can use it. Why do you want me to remove features ?... "for the greater good of having uniform functions that nobody sees" ?... Really guys ...
</p>
<blockquote class="citation">
<p>
Brett might be the well designed person to implement a nice class to deal with OA. From that we can start having nicer support for product of individual OA.
</p>
</blockquote>
<p>
We already deal with OA. All this is being built without an OA class .... My current file contains 1735 lines of code/doc to generate OA, and all that is needed are lists of lists of integers.
</p>
<blockquote class="citation">
<p>
My conclusion is: I think that this ticket is good to go as it is, but I would like that Brett gives his green light.
</p>
</blockquote>
<p>
Okay.
</p>
<p>
Nathann
</p>
TicketvdelecroixThu, 01 May 2014 14:21:34 GMT
https://trac.sagemath.org/ticket/15310#comment:48
https://trac.sagemath.org/ticket/15310#comment:48
<p>
Do you mind if we change <code>wilson_construction</code> to <code>TD_wilson_construction</code>... I thought that you like guessing what a function is doing from its name. So having a naming convention is a start!
</p>
TicketncohenThu, 01 May 2014 14:23:57 GMT
https://trac.sagemath.org/ticket/15310#comment:49
https://trac.sagemath.org/ticket/15310#comment:49
<blockquote class="citation">
<p>
Do you mind if we change <code>wilson_construction</code> to <code>TD_wilson_construction</code>... I thought that you like guessing what a function is doing from its name. So having a naming convention is a start!
</p>
</blockquote>
<p>
I am pretty sure a lot of people who find <code>wilson_construction</code> in <code>orthogonal_array.py</code> will wonder what it actually does <code>:-P</code>
</p>
<p>
If you must absolutely change something potentially deadly that will force me to fix conflicts everywhere above, what about <code>wilson_construction_of_TD</code> instead ?
</p>
<p>
Nathann
</p>
TicketncohenThu, 01 May 2014 14:27:03 GMT
https://trac.sagemath.org/ticket/15310#comment:50
https://trac.sagemath.org/ticket/15310#comment:50
<p>
By the way I have this in my file, though two entries still do not work <code>:-/</code>
</p>
<pre class="wiki">def OA_from_quasi_difference_matrix(M,G,add_col=True):
def OA_from_Vmt(m,t,V):
def OA_from_wider_OA(OA,k):
def _feasible_set_parameters(k,n,fk,fn,availability):
def OA_6_20(k,n,availability=False):
def OA_7_21(k,n,availability=False):
def OA_5_22(k,n,availability=False):
def OA_7_60(k,n,availability=False):
def OA_9_24(k,n,availability=False):
def OA_6_26(k,n,availability=False):
def OA_7_28(k,n,availability=False):
def OA_6_30(k,n,availability=False):
def OA_7_33(k,n,availability=False):
def OA_6_34(k,n,availability=False):
def OA_7_35(k,n,availability=False):
def OA_10_36(k,n,availability=False):
def OA_6_38(k,n,availability=False):
def OA_7_39(k,n,availability=False):
def OA_9_40(k,n,availability=False):
def OA_7_42(k,n,availability=False):
def OA_7_44(k,n,availability=False):
def OA_8_45(k,n,availability=False): # Broken
def OA_6_46(k,n,availability=False):
def OA_10_48(k,n,availability=False):
def OA_8_50(k,n,availability=False):
def OA_7_51(k,n,availability=False):
def OA_7_52(k,n,availability=False): # Broken
def OA_7_54(k,n,availability=False):
def OA_8_55(k,n,availability=False):
def OA_9_56(k,n,availability=False):
def OA_7_62(k,n,availability=False):
def OA_9_75(k,n,availability=False):
def OA_11_80(k,n,availability=False):
def OA_10_82(k,n,availability=False):
def OA_10_100(k,n,availability=False):
def OA_12_144(k,n,availability=False):
def OA_12_210(k,n,availability=False):
</pre>
TicketgitThu, 01 May 2014 18:57:48 GMTcommit changed
https://trac.sagemath.org/ticket/15310#comment:51
https://trac.sagemath.org/ticket/15310#comment:51
<ul>
<li><strong>commit</strong>
changed from <em>d74341411288315f13da3d4383e515b884ba7440</em> to <em>3fc79ba5be0b99e99593ff54bfa075a52cc5937c</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3fc79ba5be0b99e99593ff54bfa075a52cc5937c"><span class="icon"></span>3fc79ba</a></td><td><code>trac #15310: Merged into 6.2.rc1</code>
</td></tr></table>
TicketvdelecroixThu, 01 May 2014 20:45:31 GMTstatus changed
https://trac.sagemath.org/ticket/15310#comment:52
https://trac.sagemath.org/ticket/15310#comment:52
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
All tests pass. I am happy with this.
</p>
TicketncohenThu, 01 May 2014 20:46:12 GMT
https://trac.sagemath.org/ticket/15310#comment:53
https://trac.sagemath.org/ticket/15310#comment:53
<p>
Thanks !
</p>
TicketgitSun, 04 May 2014 16:01:36 GMTstatus, commit changed
https://trac.sagemath.org/ticket/15310#comment:54
https://trac.sagemath.org/ticket/15310#comment:54
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
changed from <em>3fc79ba5be0b99e99593ff54bfa075a52cc5937c</em> to <em>e86d26cb8126f3e557cc6a27b1727e2055f67321</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=e86d26cb8126f3e557cc6a27b1727e2055f67321"><span class="icon"></span>e86d26c</a></td><td><code>trac #15310: Merged with 6.2.rc2</code>
</td></tr></table>
TicketncohenSun, 04 May 2014 16:03:45 GMTstatus changed
https://trac.sagemath.org/ticket/15310#comment:55
https://trac.sagemath.org/ticket/15310#comment:55
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Straightforward merge conflict.
</p>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/15310#comment:56
https://trac.sagemath.org/ticket/15310#comment:56
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
TicketvbraunTue, 06 May 2014 18:05:20 GMT
https://trac.sagemath.org/ticket/15310#comment:57
https://trac.sagemath.org/ticket/15310#comment:57
<p>
Reviewer name
</p>
TicketncohenTue, 06 May 2014 18:07:50 GMTreviewer set
https://trac.sagemath.org/ticket/15310#comment:58
https://trac.sagemath.org/ticket/15310#comment:58
<ul>
<li><strong>reviewer</strong>
set to <em>Vincent Delecroix</em>
</li>
</ul>
TicketvbraunTue, 06 May 2014 23:03:07 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/15310#comment:59
https://trac.sagemath.org/ticket/15310#comment:59
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/ncohen/15310</em> to <em>e86d26cb8126f3e557cc6a27b1727e2055f67321</em>
</li>
</ul>
TicketkcrismanFri, 06 Jun 2014 16:34:12 GMTcommit deleted
https://trac.sagemath.org/ticket/15310#comment:60
https://trac.sagemath.org/ticket/15310#comment:60
<ul>
<li><strong>commit</strong>
<em>e86d26cb8126f3e557cc6a27b1727e2055f67321</em> deleted
</li>
</ul>
<p>
I'm not so sure about the <code>availability</code> argument. I know this is late to the game - see <a class="ext-link" href="https://groups.google.com/forum/#!msg/sage-devel/OPe5VJpBiB4/NlNpbHG9-sEJ"><span class="icon"></span>here</a> for some comments. I don't see why one couldn't factor out the actual part that checks whether things are available...
</p>
Ticket