$7 \cdot 115$ Let $S=\{1,2,3,4\}, a_{1}, a_{2}, \cdots, a_{k}$ be a sequence composed of numbers from $S$, and it includes all permutations of $S$ that do not end with 1, i.e., for any permutation $\left(b_{1}, b_{2}, b_{3}, b_{4}\right)$ of the 4 numbers in $S$, where $b_{4} \neq 1$, there exist $i_{1}, i_{2}, i_{3}, i_{4}$, such that
$$
a_{i_{j}}=b_{j}, j=1,2,3,4 \text { and } 1 \leqslant i_{1}<i_{2}<i_{3}<i_{4} \leqslant k .
$$

Find the minimum value of the number of terms $k$ in the sequence.
[Solution] (1) For a sequence composed of $1,2,3$, if it contains all permutations of $\{1,2,3\}$, it must have at least 7 terms.

Assume that in $1,2,3$, 3 appears last, then the first 3 must be at least the 3rd term. To include the permutations $(3,2,1)$ and $(3,1,2)$, after 3 there should be $2,1,2$ or $1,2,1$. If there is another 3 after that, there will be a total of 7 terms; if there is no more 3 after that, the only 3 must also have 3 terms before it, making a total of 7 terms.
(2) For a sequence composed of $1,2,3,4$, if it contains all permutations of $\{1,2,3,4\}$, it must have at least 12 terms.

By symmetry, we can assume that the number of terms with value 4 in the sequence is the least. If there is only 1 term that is 4, then by the previous proof, there must be at least 7 terms on both sides of it, thus the sequence must have at least 15 terms. Assume there are two 4s in the sequence, denoted as $4^{(1)}, 4^{(2)}$, where $4^{(1)}$ is to the left of $4^{(2)}$. Thus, the sequence $T$ can be represented as:
$$
T=a 4^{(1)} b 4^{(2)} c .
$$

Where $a, b, c$ are the 3 segments of the original sequence divided by the two 4s, and their lengths are denoted as $l(a)$, $l(b)$, $l(c)$. From (1) we know
$$
l(a)+l(b) \geqslant 7, l(b)+l(c) \geqslant 7 .
$$

If $l(a) \geqslant 3$ or $l(c) \geqslant 3$, then obviously $l(T) \geqslant 12$. If $l(a) \leqslant 2$, i.e., there are at most 2 terms before $4^{(1)}$, let's assume they are 1,2, then in the permutations $(2,1,4,3),(3,1,4,2),(3,2,4,1)$, the 4 can only be $4^{(2)}$, thus $c$ must contain at least one each of $1,2,3$, i.e., $l(c) \geqslant 3$. This proves that $l(T) \geqslant 12$.
(3) By symmetry, we can assume that the last term of the sequence in (2) is 1, thus removing 1 will result in a sequence that meets the requirements of the problem, and vice versa. Therefore, such a sequence must have at least 11 terms.
The sequence
$$
1,2,3,4,1,3,2,1,4,2,3
$$

meets the requirements of the problem and has exactly 11 terms.
In summary, the sequence that meets the requirements of the problem has at least 11 terms.