Are there some good algorithm to select m by three matrices which satisfies certain conditions? I would like to find an algorithm which select matrices satisfying certain conditions.

We consider integer matrices (entries of the matrices comes from $\{1,\ldots,n\}$ for some positive integer $n$) and the numbers in each row are different from each other.

Let me first explain some definitions.

We call a matrix $M$ with m rows and k columns canonical if for all $i \in [2, m]$ and $j \in [2, k]$, $M_{i,j} &gt; M_{i-1, j-1}$ and for all $i \in [2,m]$ and $j \in [1,k]$, $a_{ij} \ge a_{i-1,j}$. For example, $\left(\begin{array}{ccc}3 &amp; 5 &amp; 9\\2 &amp; 5 &amp; 8\\1 &amp; 4 &amp; 7\\1 &amp; 4 &amp; 6\end{array}\right)$ is canonical.

Let $M$ be a matrix with $k$ columns. Denote by $I_j$ the set of the elements in the $j$th row. We say that two rows $j_1, j_2$ of $M$ i-interlacing if $|J_{j_1} \backslash J_{j_2}|=|J_{j_2} \backslash J_{j_1}|=i$ and $J_{j_1}\backslash J_{j_2} = \{a_1,a_2,\ldots,a_i\}$, $J_{j_2} \backslash J_{j_1} = \{b_1,b_2,\ldots,b_i\}$, either $a_1 &lt; b_1&lt;a_2&lt;b_2 &lt; \cdots &lt; b_{i-1} &lt;a_i &lt; b_i$ or $b_1&lt;a_1&lt;b_2&lt;a_2 &lt; \ldots &lt; a_{i-1}&lt;b_i&lt;a_i$. In particular, if two rows of a matrix are identical, then we say that the two rows are $0$-interlacing.

For example, the first row and the second row of $\left(\begin{array}{ccc}3 &amp; 5 &amp; 9\\2 &amp; 5 &amp; 8\\1 &amp; 4 &amp; 7\\1 &amp; 4 &amp; 6\end{array}\right)$ are $2$-interlacing. The third row and the fourth row of the matrix are $1$-interlacing. 

For a matrix $M$ with entries in $\{1, \ldots, n\}$, denote $x=x(M)=(x_1, \ldots, x_n)$, where $x_i$ is the number of entries in $M$ which equal to $i$. Denote $q(M)=\sum_{i=1}^n x_i^2 + \frac{2-k}{k^2} (\sum_{i=1}^n x_i)^2$, where $k$ is the number of columns of $M$. For example, let $M=\left(\begin{array}{ccc}3 &amp; 5 &amp; 9\\2 &amp; 5 &amp; 8\\1 &amp; 4 &amp; 7\\1 &amp; 4 &amp; 6\end{array}\right)$. Then $x(M) = (2,1,1,2,2,1,1,1,1)$ and $q(M)=2$.

I would like to find all $m \times 3$ matrices $M$ with entries in $\{1, \ldots, 9\}$ which satisfy the following conditions:

(1) in each row of $M$, any two entries are different from each other; the numbers in each row are increasing from left to right;

(2) any two rows of $M$ are $i$-interlacing for some $i \in \{0,1,2,3\}$;

(3) there are two rows of $M$ which are $3$-interlacing;

(4) $M$ is canonical;

(5) $q(M)=2$.

In the cases of $m=2,3,4$, I use many for loops to find out all such matrices. But when $m \ge 5$, it takes infinite time. Is there some fast algorithm to find out all the matrices which satisfy the conditions? Thank you very much.
A simple way to deal with this problem&mdash;which perhaps can hardly be called a "good algorithm", but nonetheless provides a variety of performance improvements&mdash;is to treat it as a constraint satisfaction / combinatorial search problem and apply backtracking. Each matrix entry branches the search tree 9 ways, but many of these subtrees can be trivially eliminated because they immediately violate one of the conditions.

Take the $m = 5$ case that you got stuck on as an example. For condition 1, note that already there are only $\binom{9}{3}^5 = 4,182,119,424$ matrices of size 5x3 with elements in [1..9] which have elements strictly increasing from left to right in each row. It's $\binom{9}{3}^5$ because condition 1 is equivalent to, for each row, choosing 3 distinct elements from [1..9]. You can of course iterate over such rows with

for i in 1 to 7, for j in i + 1 to 8, for k in j + 1 to 9

Moreover, conditions 2 and 4 can be checked as you are generating the rows, rather than only checking these conditions once you have the entire matrix. This should drastically prune the search tree.

Tassle adds (and provides this sample code):


  You can also prune on condition (5) by first computing all possible profiles $x(M)$ which lead to $q(M)=2$, and then trying to find all satisfying matrices with a specific profile. Out of all 490314 ways to choose 15 numbers in {1...9}, only 84 lead to $q(M)=2$. In fact, using this, even python on my quite slow machine can manage m = 5 in a reasonable time. 


This sort of brute forcing is also embarrassingly parallel and requires hardly any memory, so consider dividing the space of matrices among however many CPU cores you have.