0
$\begingroup$

I'm looking for a way to enumerate the $k$-permutations of a $n$ element set; that is, if $A=\left\{1, \dots, n\right\}$ and $K=\left\{(p_1, \dots, p_k)\mid p_i\in A\wedge i\neq j\implies p_i\neq p_j\right\}$; then I'd like a bijection

$f:\left\{1, \dots, \frac{n!}{(n-k)!}\right\}\to K$

along with it's inverse. In particular I'd like something computable rather than enumerative since clearly I could enumerate them by hand, but this becomes memory inefficient for large $n$ and $k$.

1 Answers 1

1

You could us a partial Lehmer code: A number in mixed base $n,\dotsc,n-k+1$ that specifies which of the remaining slots is to be used in each of $k$ selection steps.

  • 1
    I think I see (I use this for permutations of $n$ elements, so the $k=n$ case), just use the first $k$ digits and you still have a unique representation..2012-10-26