Shuffle algorithms can handle this easily, although those may fail with sufficiently large N and K that won't fit in memory. Several unbiased O(n) shuffle algorithms exist, such as the Fisher-Yates shuffle. If you're using C++ there is an implementation of that std::shuffle() which was previously known as std::random_shuffle() if you're using an old compiler.
Even if you can't hold N in memory, if you could hold a count of N values in an array then it becomes your index into N. Add values from 0 to N-1 as all index values, shuffle them, and pick K values.
If you can't reasonably make a list of length N, this comes to mind:
-
Select random offset numbers. Select K numbers; pull from 0 to N-1, then from 0 to N-2, then from 0 to N-3. etc. Use a non-biased algorithm for this.
-
Compute the index values. Iterate through the offset numbers. The initial value is the random number, then iterate over the prior index values in ascending order; if an existing index value is lower than the value you are considering, increment your current value under consideration. When you've incremented up to the current value, it becomes the new index. In other words, the offset value means to advance that many unused numbers.
-
Look up the index values from pool N for the final list.
As an example of N=15 and K=5:
1. Using a random number generator I get the following five values from the first step: { 1, 9, 4, 11, 6 }
2. Next I compute the index values:
Index 1. { 1 }
Offset 9 finds it is greater then index 1, so becomes index 10 { 1, 10 }
Offset 4 finds it is greater than index 1, 10 is greater, so becomes index 5. { 1, 5, 10 }
Offset 11 finds it is greater than 1, 5, and 10, so becomes index 14. { 1, 5, 10, 14 }
Offset 6 finds it is greater than 1 and 5, so becomes index 8. { 1, 5, 8, 10, 14 }
3. Look up the values N[1], N[5], N[8], N[10], N[14]. This is your result.
If ordering were important, maintain a parallel ordered list where each index is added in the same order they were generated from the initial offset list.
And for N=15 and K=15 so you should see every item:
Offset numbers { 1 9 4 11 6 4 6 7 2 3 2 0 2 0 0 }
Index values as they grow:
(unused offset 1) 1
(+9) 1 10
(+4) 1 5 10
(+11) 1 5 10 14
(+6) 1 5 8 10 14
(+4) 1 5 6 8 10 14
(+6) 1 5 6 8 10 11 14
(+7) 1 5 6 8 10 11 13 14
(+2) 1 3 5 6 8 10 11 13 14
(+3) 1 3 5 6 7 8 10 11 13 14
(+2) 1 3 4 5 6 7 8 10 11 13 14
(+0) 0 1 3 4 5 6 7 8 10 11 13 14
(+2) 0 1 3 4 5 6 7 8 10 11 12 13 14
(+0) 0 1 2 3 4 5 6 7 8 10 11 12 13 14
(+0) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
If you want that in random order, preserve the order of the offsets: { 1 10 5 14 8 6 11 13 3 7 4 0 12 2 9 }
Or if you prefer to see it from the perspective of the UNUSED pool:
(position 1) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
(9) 0 2 3 4 5 6 7 8 9 10 11 12 13 14
(4) 0 2 3 4 5 6 7 8 9 11 12 13 14
(11) 0 2 3 4 6 7 8 9 11 12 13 14
(6) 0 2 3 4 6 7 8 9 11 12 13
(4) 0 2 3 4 6 7 9 11 12 13
(6) 0 2 3 4 7 9 11 12 13
(7) 0 2 3 4 7 9 12 13
(2) 0 2 3 4 7 9 12
(3) 0 2 4 7 9 12
(2) 0 2 4 9 12
(0) 0 2 9 12
(2) 2 9 12
(0) 2 9
(0) 9