Good point. Storing a number of magnitude n! will take n log n bits, and storing n numbers up to n will also take n log n bit.

In other words, good old Fisher Yates, storing the resulting permutation, and a simple lookup is probably the way to go.