Skip to content

Instantly share code, notes, and snippets.

@gau820827
Created Oct 7, 2018
Embed
What would you like to do?
/*
input: N, M
The function should print out M ordered numbers sampled from 0 ~ N - 1
The probability for each combination should be the same
For example -> N = 3, M = 2
The probability for [1,2] and [1,3] should be the same.
*/
#include <stdlib.h>
#include <iostream>
#include <set>
using namespace std;
unsigned int global_seed = 13777;
// Time: O(N) solution, Space: O(M) or O(1) if don't save the results
void SampleNumbers1(int N, int M) {
for (int i = 0; i < N; ++i) {
if (rand_r(&global_seed) % (N - i) < M) {
cout << i << endl;
--M;
}
}
return;
}
// Time: O(MlogM), Space: O(M) solution
// Might have collision issue, especially when M is near N
void SampleNumbers2(int N, int M) {
set<int> s;
while (s.size() < M) {
int n = rand_r(&global_seed) % N;
s.insert(n);
}
for (const int& ele : s) {
cout << ele << endl;
}
return;
}
// Robert Floyd's Tiny and Beautiful Algorithm
// Time: O(MlogM), Space: O(M) solution without collision
void SampleNumbers3(int N, int M) {
set<int> s;
for (int i = N - M; i < N; ++i) {
int n = rand_r(&global_seed) % (i + 1);
if (s.find(n) == s.end()) {
s.insert(n);
} else {
s.insert(i);
}
}
for (const int& ele : s) {
cout << ele << endl;
}
return;
}
int main() {
cout << "Enter N, M: ";
int N, M;
cin >> N >> M;
cout << "SampleAlgo1" << endl;
SampleNumbers1(N, M);
cout << "SampleAlgo2" << endl;
SampleNumbers2(N, M);
cout << "SampleAlgo3" << endl;
SampleNumbers3(N, M);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment