3 ms·
Again, I am confused. Why doesn't this snippet solve the problem? void increasingRandomSequence(arrayptr, base, k, n) { if (k == 0) return; int
by kutkloon7 11y ago
Again, I am confused. Why doesn't this snippet solve the problem?
void increasingRandomSequence(arrayptr, base, k, n)
{
if (k == 0) return;
int i = randInt(n - k);
*(arrayptr) = base + i;
increasingRandomSequence(arrayptr + 1, base + i + 1, k - 1, n - (i + 1));
}
increasingRandomSequence(hand, 0, k, n) fills the array hand with a sequence which is picked with uniform distribution over all increasing sequences of length k with numbers in [0, n - 1].
This is O(k), and we can shuffle this in O(k). Why doesn't this solve the problem?
- anonymoushn 11y agoIt looks like this dramatically undersamples the beginning. Like if I ask for 1000 numbers out of 10,000, the very first number you provide will be (on average) nearly halfway through the list.
- dalke 11y agoThe method is on-line, that is, it doesn't need to know "n". Assuming I translated your above code correctly into Python, as: import random def increasingRandomSequence(base, k, n): while k > 0: i = random.randrange(n - k + 1) yield base + i base += i+1 k -= 1 n -= i+1 then I checked the above using: N = 6 counters = [0] * N for i in range(100000): for value in increasingRandomSequence(0, 5, N): counters[value] += 1 print(counters) and found a strong bias towards larger numbers. The counts are: [50033, 75037, 87438, 93686, 96900, 96906] which means 5 is in the hand much more often than 0.
- kutkloon7 11y agoYou guys are right, it's uniform in the first digit of the sequence which is actually not uniform at all... Thanks for pointing it out!