*********************************************this is c++ program*********************************************

A set of numbers is a unique set of numbers if and only if no number appears more than once in the set.

{1, 6, 9, 3, 2} is a unique set of numbers

{2, 6, 9, 3, 2} is not a unique set of numbers

The two programs simulate LOTTO by generating unique sets of random numbers until the last set equals the first set. Because ordered set comparison is much faster than unordered set comparison, one program sorts the numbers in a set before it compares pairs of sets. However, sorting the sets takes time too. Which program is faster? Is sort time+ search time with sorting less than search time without sorting?

**********************************************************************************

//lotterysimulation1.cpp

#include

#include

#include

#include

#include

#include

using namespace std;

vector uniqueRandomFill(size_t m, size_t n);

bool kEqual(const vector& v1, const vector& v2, size_t k);

size_t gamble(const vector& original, size_t m, size_t n);

int main()

{

size_t ubound = 20;

for (size_t counter = 1; counter <= ubound; counter++)

{

vector v = uniqueRandomFill(counter, ubound);

cout << setw(2) << counter << ": " << gamble(v, counter, ubound) << endl;

}

system("pause");

return 0;

}

vector uniqueRandomFill(size_t m, size_t n)

{

uniform_int_distribution u(1, n);

static default_random_engine e((unsigned)time(nullptr));

vector v(m);

for (size_t i = 0; i < m; i++)

{

size_t value;

while (find(v.begin(), v.end(), (value = u(e))) != v.end())

;

v[i] = value;

}

return v;

}

bool kEqual(const vector& v1, const vector& v2, size_t k)

{

size_t size1 = v1.size();

size_t size2 = v2.size();

size_t count = 0;

for (size_t m1 : v1)

for (size_t m2 : v2)

if (m1 == m2) ++count;

return count >= k;

}

size_t gamble(const vector& original, size_t m, size_t n)

{

size_t compares = 0;

vector selection;

do

{

selection = uniqueRandomFill(m, n);

compares++;

} while (!kEqual(original, selection, m));

return compares;

}

**********************************************************************************

//lotterysimulation2.cpp

#include

#include

#include

#include

#include

#include

using namespace std;

vector uniqueRandomFill(size_t m, size_t n);

bool kEqual(const vector& v1, const vector& v2, size_t k);

size_t gamble(const vector& original, size_t m, size_t n);

int main()

{

size_t ubound = 20;

size_t fwidth = 2;

for (size_t counter = 1; counter <= ubound; counter++)

{

vector v = uniqueRandomFill(counter, ubound);

cout << setw(fwidth) << counter << ": " << setw(6) << gamble(v, counter, ubound) << endl;

}

system("pause");

return 0;

}

vector uniqueRandomFill(size_t m, size_t n)

{

uniform_int_distribution u(1, n);

static default_random_engine e((unsigned)time(nullptr));

vector v(m);

for (size_t i = 0; i < m; i++)

{

size_t value;

while (find(v.begin(), v.end(), (value = u(e))) != v.end())

;

v[i] = value;

}

sort(v.begin(), v.end());

return v;

}

bool kEqual(const vector& v1, const vector& v2, size_t k)

{

size_t size1 = v1.size();

size_t size2 = v2.size();

size_t count = 0;

size_t idx1 = 0;

size_t idx2 = 0;

while (idx1 < size1 && idx2 < size2 && k + idx1 <= size1 + count && k + idx2 <= size2 + count)

{

if (v1[idx1] < v2[idx2]) ++idx1;

else if (v2[idx2] < v1[idx1]) ++idx2;

else if (v1[idx1] == v2[idx2])

{

++idx1;

++idx2;

++count;

}

}

return k <= count;

}

size_t gamble(const vector& original, size_t m, size_t n)

{

size_t compares = 0;

vector selection;

do

{

selection = uniqueRandomFill(m, n);

compares++;

} while (!kEqual(original, selection, m));

return compares;

}