Given an array of n unique integers (1 to n), write an algorithm to draw a random combination of k distinct numbers (n >= k). (This problem comes from Core Java Vol I as an example.)
Unknown: A way to draw k distinct integers out of n distinct integers.
Data: An array of integers 1 to n.
Constraint: k numbers must be distinct and randomly picked.
A straightforward solution would be:
- Randomly pick one number out of the an array
- If this number is not picked before, add it to the result. Return the result if we have k numbers.
- Otherwise, back to step 1.
Q: So what is the time complexity of this solution?
A: If we are unlucky, in the worst case, O(k^2) and if k close to n, O(n^2).
Q: How so?
A: At some point, we will have problem selecting a number that’s not in the result set. The first number is easy, just once. The second, if unlucky, twice. The third, if unlucky, 3 times since the first 2 times picked something in the result set…so up to k numbers, it can take 1+2+3+…+k picks which is approximately O(k^2). If k is close to n, then we have a O(n^2) algorithm. check the link at the bottom for the code.
Q: Alright, can we make it faster? Say let’s make it O(n) time and you cannot use additional space except for the result set.
A: Hmm, the bottleneck of the previous solution is that every time we pick a number, we have to check if it exists in the result set. If it does, we have to go back and pick again. If we can skip this step it will be faster.
Q: What do you mean by skipping this step?
A: I mean that every time we pick a number, it is guaranteed not picked before.
Q: How do we do that?
A: Hmm. we need to keep track of what has not been picked instead. Since we cannot use additional space, I assume that we have to do something on the original array. I can replace the picked number with some special value like n+1, but this sounds useless since if I happened to pick this number, I would have to choose again, exactly like before. I don’t know…
Q: OK, in what situation can we safely draw an unpicked number?
A: If the array only contains unpicked numbers, we can do that safely. But again, I don’t think we can recreate a new array to exclude the picked one in every pass. That’s O(n^2) again.
Q: True. So why can’t we draw the numbers safely now? What’s the matter?
A: Because there are picked values between unpicked ones.
Q: Good. You mentioned about excluding them. Is there a way to do that without creating a new array?
A: I suppose I can re-arrange the array? For example, if I picked the number at index i, I can move the numbers from i+1 to n-1 forward. But then I should pick a random index between 0 to n-1 (exclusive). Wait, this is still O(n^2)…
Q: Do we have to move all the elements after index i? Can we reduce this O(n) move to a O(1) move?
A: O(1)? So I should move only 1 element instead. But which one…
Q: Let’s use an example: 1,2,3,4,5 Say we picked 3. In your case, we change the array to 1,2,4,5,5 and then we pick from index 0 to 3 next time. We do the move because we want to make sure next time we are choosing from 1,2,4,5. So is there another way to do it?
A: Yes! I can move the last element to that position to achieve the same effect! So every time after the pick, I move the last element within the current range to the picked position then reduce the range by 1.
Q: That’s right 🙂
Link to the code: https://gist.github.com/jingz8804/53955bbaf817a6c2e179