Writing a method that outputs a different uniqe permutation of a number every time it's called

I got this interview question and I am still very confused about it. The question was as the title suggest, i'll explain.

You are given a random creation function to use.

the function input is an integer n. let's say I call it with 3.

it should give me a permutation of the numbers from 1 - 3. so for example it will give me 2, 3 , 1.

after i call the function again, it won't give me the same permutation, now it will give me 1, 2, 3 for example.

Now if i will call it with n = 4. I may get 1,4,3,2.

Calling it with 3 again will not output 2,3,1 nor 1,2,3 as was outputed before, it will give me a different permutation out of the 3! possible permutations.

I was confused about this question there and I still do now. How is this possible with a normal running time ? As I see it there has to be some static variable that remembers what was called before after the function finishes executing. So my thought is creating a static hashtable (key,value) that gets the input as key and the value is an array of the length of the n!. Than we uses the random method to output a random instance out of these and moves this instance to the back so it will not be called again, thus keeping the output unique.

The space time complexity seems huge to me. Am I missing something in this question ?