Finding the kth element of a permutation
Problem statement

Your question is unclear, but here is how I interpret it:


  Input: a positive integer $n$, and $k$ distinct values $x_1,\dots,x_k \in \{1,2,\dots,n\}$
  Output: the values $\pi(x_1),\pi(x_2),\dots,\pi(x_k)$, where $\pi$ is a random permutation on $\{1,2,\dots,n\}$


You are looking for an efficient algorithm to solve this problem.

An efficient solution

If that is indeed what you are looking for, there is a very efficient way to solve this problem.  Basically, all you need to do is randomly choose $k$ distinct integers from the set $\{1,2,\dots,n\}$.  This is sampling without replacement.  Here is a simple algorithm:


Initialize $S$ to be the empty set.
For $i=1,2,\dots,k$:


Pick $r$ uniformly at random from $\{1,2,\dots,n\}$.  If $r\in S$, pick a new $r$ (and keep repeating until $r \notin S$).
Set $x_i$ to $r$, and add $r$ to $S$.



You can use any number of data structures for storing the set $S$; it could be a bitvector of length $n$, or a hashtable.  (A bitvector is probably better if $k$ is not too much smaller than $n$, say $k \ge n/64$ or so; a hashtable is probably more efficient if $k$ is small compared to $n$.)

Performance analysis

If $k \le n/2$, the expected running time is linear in $n$, so this is very efficient.

If $k \ge n/2$, there are better algorithms.  For instance, once you reach $i \ge n/2$, then rather than choosely uniformly, you can choose uniformly at random from $\overline{S}$ (the complement of $S$).  If you use the right data structures, you can make the expected running time be linear in $n$.  (Basically, once $i\ge n/2$, you compute $\overline{S}$ and throw away $S$.  In each step, you choose a random element of $\overline{S}$, then remove it from $\overline{S}$.  Choosing a random element of a set can be done in $O(1)$ expected time.)