What algorithm is a good to search a lotto design?

Question

I'm interested what kind of algorithm would be suitable to find a lotto design? I saw that is has been proven that $L(39,7,4,7)=329$. This notation is explained in http://web.archive.org/web/20070824014211/http://www.maths.qmul.ac.uk/~pjc/csgnotes/LottoDesigns.pdf and it goes as follows:

In a lotto, one chooses seven distinct numbers $n_1<\ldots < n_7$ from the set $\{1,\ldots,39\}$ and forms a tuple $(n_1,\ldots,n_7)$ called row. It is possible to choose 329 of such rows such that for any arbitrary row $(n_1,\ldots,n_7),$ the set of those 329 rows contains at least one row $(m_1,\ldots,m_7)$ such that $$|\{n_1,n_2,n_3,n_4,n_5,n_6,n_7\}\cap \{m_1,m_2,m_3,m_4,m_5,m_6,m_7\}|\geq 4?$$ I think this result is due to Hämäläinen based on the inequality $$L(39,7,4,7) \leq L(16,7,4,4) + L(23,7,4,4)\leq 76+253=329$$ that I'm not familiar. Now the question:

Is it possible to list those $329$ rows from the design $(39,7,4,7)$ explicitly with reasonable time? Is simulated annealing the best algorithm to list those rows?

I asked this on https://stackoverflow.com/questions/18486523/what-algorithm-is-a-good-to-search-a-lotto-design but it turned out a bad question there.

Answer 1

The question appears to quote in parts my answer at AOPS dated Jul 15, 2011, including the presentation link. What puzzles me though is that here the OP asks for a particular lotto design $(39,7,4,7)$, while my answer was constructive and, in fact, provided all information for obtaining such a design. Here is how it goes.

The slide #9 in the linked presentation constructively explains the inequality: $$L(39,7,4,7) \leq L(16,7,4,4) + L(23,7,4,4)\leq 76+253=329.$$ Since $L(16,7,4,4) = C(16,7,4)$ and $L(23,7,4,4) = C(23,7,4)$ are covering designs, we can obtain the corresponding blocks from La Jolla Covering Repository:

• $C(16,7,4) \leq 76$ (blocks)
• $C(23,7,4) = 253$ (blocks)

Namely, to get a lotto design $(39,7,4,7)$ with 329 blocks, one can just take the union of the blocks for $C(16,7,4)$ and the blocks for $C(23,7,4)$, where the elements of the latter blocks are all increased by 16. The resulting blocks are:

 1  2  3  4  6  8 16                      \
 ...                                       } blocks from C(16,7,4)
 7  9 12 13 14 15 16                      /
 1+16  2+16  3+16  4+16  5+16  6+16  7+16 \
 ...                                       } blocks from C(23,7,4),
 7+16 11+16 15+16 17+16 18+16 19+16 20+16 /  with elements increased by 16

Answer 2

A $L(v,k,p,t)$ lotto design is a subset of $\binom{V}{k}$, where $V = \{1,\ldots,v\}$ and $\binom{V}{k}$ is the set of all $k$-element subsets of $V$. Since $v$ is a natural number, the set of all subsets of $\binom{V}{k}$ is finite. So there is the algorithm to enumerate all these finitely many subsets, and check then for the design property. This "naive algorithm" will terminate after a finite number of steps. However, due to combinatorial exposion the effort is huge, and you won't witness this algorithm to terminate in any but the smallest cases.

A more refined approach is to do a backtracking search: You start with the full set $\binom{V}{k}$ and try to remove a single element in each layer of the search tree. In this way, you avoid touching many unnecessary subsets of $\binom{V}{k}$.

A huge obstacle in such kinds of problems are isomorphic copies: If you have a lotto design, any permutation of the base set $V$ will again give you a lotto design. This means that without any counter-measures, your search algorithm typically will return millions of copies of essentially the same lotto design. The techniques to reduce or avoid isomorphic copies of the search tree are quite sophisticated, and often, it is not clear what should be the most efficient approach.

These techniques allow you to completely enumerate all lotto designs of larger parameters than with the naive algorithm. But still, the search space grows exponentially, and soon it won't be possible to solve the problem by complete enumeration. So for larger parameters, "record" designs are typically not produced by a complete enumeration approach. Instead, some additional properties are introduced, or some kind of a heuristic is used.

The above discussion is about a general method to construct lotto designs. I don't know how exactly the result L(39,7,4,7) = 329 has been proven. Typically, it is done by a combination of theoretical arguments which reduce the size of the search space, and a computer enumeration which is able to enumerate all the remaining possibilities.