3 ms·
If you don’t know k beforehand, you have to (eventually) handle the case where k is large, possibly even equal to n. If it turns out to be equal to n, you have
by Someone 7y ago
If you don’t know k beforehand, you have to (eventually) handle the case where k is large, possibly even equal to n.
If it turns out to be equal to n, you have to generate a permutation.
If it isn’t, you don’t need to, but you need to keep enough information around, in case it turns out that you need.
For example, by the time you’ve generated 2⁶³ integers in the range 1…2⁶⁴, you need to know which 2⁶³ integers still are ‘available’.
I think you can’t do that more compactly than by just picking the permutation to generate at start (whether you can efficiently determine the k-th number in that permutation is a separate problem)