I'm looking for a set of permutations over $n$ elements $\mathcal{P}=\{P_1,P_2,...,P_r\}$ of minimal size such that for every ordered subset of size $k$, $S=<x_1,x_2,...,x_k>, (x_i \in [n])$, there exists a permutation $P \in\mathcal{P}, $ such that $P(x_1)<P(x_2)<...<P(x_k)$.
A simple probabilistic argument can show that such family of size $r=k!\cdot k\cdot log(n)+1$ exists:
Suppose we draw $r$ random permutations. The chance that some specific $<x_1,...,x_k>$ is not ordered by non of the permutations is $(1-\frac{1}{k!})^r$.
Using the union bound, the chance that any ordered k tuple will not be ordered is bounded by:
$(1-\frac{1}{k!})^r\cdot$$ n\choose k$$\cdot k!<(1-\frac{1}{k!})^r\cdot n^k < n^k\cdot e^{-r/k!}$
If we demand that the probability will be less than 1 (which ensures such family exists), we get the desired size, $r>k!\cdot k\cdot log(n)$.
The question is:
Is there an explicit build for such family? is it computable in $O(k!\cdot poly(n))$ time?
This question might have been referred to somewhere in a different name, so if anyone is familiar with it, a reference will be great.
Edit: Andreas gave a nice build for parametric $k$.
What about the case that $k$ is a small, fixed number?
If $k=2$, then it's easy: take $\mathcal{P}=\{<1,2,...,n>,<n,n-1,...,1>\}$.
Can we build $O(1)$ sized 3-perfect permutation family? higher fixed $k$?