#include<iostream.h> // Header file used for input and output.
#include<iomanip.h> // Header file used to manipulate output.
#include<stdlib.h> // Header file containing random function.
#include<fstream.h> // Header file for using files.
#include<time.h> // Header file for calculating iteration times.
#include<stl.h> // Header file for STL (Standard Template Libraries) <set, multiset>.
#include<math.h> // Header file for mathematical functions.
long double fact (int);
long int round (const long double);
bool ValidTicket (const short int *, const short int &, const short int &);
// Compute the factorial of n (i.e. n!).
long double fact (int n) {
if (n <= 1) return 1; // Stop recursion.
else return n * fact(n - 1); // (n > 1)
}
// Rounds a number to the nearest integer to avoid possible numerical truncation errors.
long int round (const long double n) {
long int flrnum
= (long int)floor(n
); if (n - flrnum < 0.5) return flrnum;
else return (long int)ceil(n
); // (n - flrnum >= 0.5) }
// Determine whether a ticket (n-set) is valid (ticket contains no double numbers).
bool ValidTicket (short int *ticket, const short int &m, const short int &n) {
multiset<short int, less<short int> > index;
multiset<short int, less<short int> >::iterator i;
for (short int counter = 0;counter < n;counter++) {
index.insert(ticket[counter]); // Add number to index.
if (index.count(ticket[counter]) > 1)
return false; // Ticket is invalid.
}
i = index.begin(); // Arrange ticket elements lexicographic ally.
for (short int counter = 0;i != index.end();ticket[counter++] = *i++);
return true; // Ticket is valid.
}
int main () {
short int m, n, k, L; // Variables containing the lottery parameters <m,n;k> and playing set cardinality L.
cout << endl << "\t CLASSICAL RANDOM ALGORITH." << endl << endl; cout << "Please specify the following parameters for the lottery (m,n;k):" << endl; cout << "m = "; cin >> m;
cout << "n = "; cin >> n;
cout << "k = "; cin >> k;
// If the user specified invalid lottery parameters.
if ((n > m-1) || (k > n-1) || (m < 3) || (n < 2) || (k < 1)) {
cout << endl << "Invalid lotter parameters entered." << endl;
return 0; // Exit program.
}
long int NumTickets, r = 0, CurrentTicketNumber, NumDominated, MaxDominated = 0, iter = 0;
time_t StartTime; // Trace execution time.
int CurrentTicket[n], CurrentNumber = n, size, Counter1, Counter2; // Reference to current ticket/vertex investigated.
fstream PlayingSetInfo("PlayingSet.Info", ios::out); // Playing set info file.
if (!PlayingSetInfo) { // Check whether the file "PlayingSet.Info" could be opened.
cout << "The file \"PlayingSet.Info\" could not be opened." << endl;
return 0; // Exit program.
}
// Compute the number of vertex set cardinality and degree of regularity of the lottery graph G<m,n;k>.
NumTickets = round(fact(m)/(fact(n)*fact(m-n)));
for (int i = k;i < n;i++)
r += round((fact(n)/(fact(n-i)*fact(i)))*(fact(m-n)/(f act(n-i)*fact(m-2*n+i))));
cout << endl << "Order of the lottery graph G(" << m << "," << n << ";" << k << ") is " <<
NumTickets << " and it is "
<< r << " regular." << endl;
cout << endl << "Playing set cardinality = "; cin >> L;
if (L < 1) // Invalid playing set cardinality specified.
return 0; // Exit program.
short int DomArray[L][n], Intersect, dcounter, tcounter; // Playing set, number of elements
common to 2 tickets/vertex labels (intersection ).
srandom(time(NULL
)); // Initialize the pseudo random number generator. StartTime
= time(NULL
); // Capture start of executed time.while (iter < 1000) { // This value may be changed, depending on the number of iterations preferred.
for (short int i = 0;i < L;i++) // Generate pseudo random playing set.
do
for (short int j = 0;j < n;j++)
DomArray[i][j] = ((short int)(((random())/(float)RAND MAX)*m)+1); // Generation random ticket.
while (!ValidTicket(DomArray[i], m, n)); // Check whether generated ticket is valid.
NumDominated = 0;
// Generate the first lexicographic lottery Ticket [1,2,...,n].
for (int i = 1;i <= n;i++) CurrentTicket[i-1] = i;
// Determine resource utilisation ΨR (m, n; k) of playing set>
for (long int i = 1;i <= NumTickets;i++) {
Intersect = 0;
// Check whether current ticket is dominated.
for (short int DomTicketNum = 0;(DomTicketNum < L) && (Intersect < k);DomTicketNum++)
for (short int DomTicketNum = 0;(DomTicketNum < L) && (Intersect < k);DomTicketNum++) {
Intersect = dcounter = tcounter = 0;
while ((dcounter < n) && (tcounter < n) && (Intersect < k))
if (DomArray[DomTicketNum][dcounter] < CurrentTicket[tcounter]) dcounter++;
else if (DomArray[DomTicketNum][dcounter] > CurrentTicket[tcounter]) tcounter++;
else { // (DomArray[Dom TicketNum][dcounter] == CurrentTicket [tcounter])
Intersect++; dcounter++; tcounter++;
}
if (Intersect == k) // Check whether current vertex/ticket is dominated by playing set.
NumDominated++;
}
CurrentTicket[CurrentNumber-1]++; // Generate next lexicographic ticket/vertex label.
if (CurrentTicket[CurrentNumber-1] > m) {
CurrentTicket[CurrentNumber-1]--;
while ((CurrentNumber > 0) && (CurrentTicket[CurrentNumber-1] == m-(n-CurrentNumber)))
CurrentNumber--;
CurrentTicket[CurrentNumber-1]++;
for (int j = CurrentNumber;j < n;j++) CurrentTicket[j] = CurrentTicket[j-1] + 1;
CurrentNumber = n;
}
}
if (NumDominated > MaxDominated) { // New maximum resource utilisation found.
// Write the (current best) playing set info to file.
PlayingSetInfo.seekp(0, ios::beg); // Search to the beginning of the output file.
PlayingSetInfo << endl << "Lottery (" << m << "," << n << ";" << k << ") :" << endl << endl;
PlayingSetInfo << "Playing set :" << endl;
for (int i = 0;i < L;i++) {
for (int j = 0;j < n;j++)
PlayingSetInfo << setiosflags(ios::right) << setw(3) << DomArray[i][j];
PlayingSetInfo << endl;
}
PlayingSetInfo << "Playing set dominates " << NumDominated << "/" << NumTickets << " vertices ("
<< setw(8)
<< setprecision(4) << setiosflags(ios::fixed|ios::showpoint) << (float)NumDominated/NumTickets*100
<< "%)." << endl;
MaxDominated = NumDominated; // Store new maximum resource utilisation.
}
iter++; // Next iteration.
}
PlayingSetInfo.close(); // Close the playing set info file. cout << "Time elapsed = " <<
time(NULL
)-StartTime
<< endl
; return 0; // Exit program. }