質問: 2$ (a $3\times 3$ grid, placing 2 markers in each row) First, Player One chooses two columns in each row, and places markers in those cells: $$ \begin{array}{|c|c|c|} \hline X&X&\\ \hline X&X&\\ \hline &X&X\\ \hline \end{array} $$ Player Two then checks the row pairs $(1,2),(1,3)$ and $(2,3)$. The first pair shares 2 columns, and the last two pairs share only 1 column, so Player Two selects rows 1 and 2 because they have the most matching columns (2). I am looking for a general strategy for placing markers given $(m,n,r)$. The strategy need not be optimal as it is intended to be uses in stochastic local search. This problem arises as a sub problem in investment design in finance. An easy to calculate lower bound exist, and for almost all instances I have seen a solution where the similarity is this lower bound exist. Example instances: $(10,30,9)$ has lower bound 2. $(11,22,10)$ has lower bound 4. The instance $(10,8,3)$ has a lower bound of 2 with the following solution: $$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline X&X&X&&&&&\\ \hline X&X&&X&&&&\\ \hline X&X&&&X&&&\\ \hline X&X&&&&X&&\\ \hline X&X&&&&&X&\\ \hline X&X&&&&&&X\\ \hline X&&X&X&&&&\\ \hline X&&X&&X&&&\\ \hline X&&X&&&X&&\\ \hline X&&X&&&&X&\\ \hline \end{array} $$ The most similar rows (1 and 2, among others) share 2 markers and the solution is therefore optimal.
回答: The following brutish algorithm does okay, it might be a start. It generates an optimal solution for $(10,8,3)$ and gets scores of 3 and 6 for $(10,30,9)$ and $(11,22,10)$, respectively by building the board one row at a time. To create the first row, place markers in the first $r$ columns. To generate the next row, $R$, start with a row with no markers. While $R$ has less than $r$ markers: * For each column $i$, create a candidate row $R_i$ which is $R$ but with a marker added to column $i$. (If $R$ already has a marker in column $i$, ignore this candidate). * Score $R_i$ pairwise against each other row already added to the board, note the highest pairwise scoring as $S_i$. * Among the rows already in the board, count how many also have a marker in column $i$, denote this count as $C_i$. * Choose the column $c$ so that $S_c \le S_j$ for any $j \ne c$. If there are two columns with the same minimum score, choose the column with the lower $C_c$. * Add a marker into column $c$. Do this until all the rows have been generated. For $(10,8,3)$ this generates the following table. Markers are numbered as they are added: \begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&2&3&&&&&\\ \hline &&&1&2&3&&\\ \hline 3&&&&&&1&2\\ \hline &1&&2&&&3&\\ \hline &&1&&2&&&3\\ \hline 2&3&&&&1&&\\ \hline &&1&2&3&&&\\ \hline &&3&&&1&2&\\ \hline 3&2&&&&&&1\\ \hline &&&1&3&&&2\\ \hline \end{array} A gist with a Python implementation can be found here: