What if union of disjoint sets results in universal set?

C++ Progam

• I need to write a C++ program that does the following: In the mathematical theory of sets, a set is defined as a collection of distinct (no two alike) items of the same type. In some programming languages, sets are a built-in data type. C++ does not have a built-in set type, though the Standard Template Library does provide a set type as an add-on to the language. We can simulate a set in any language using a one-dimensional array. There are several operations that can be performed on sets. We will consider only three of them: union, intersection, and difference. These are binary operations requiring two sets as operands. The union of two sets A and B (A + B), is a set that contains elements that are in A or in B or in both. The intersection of two sets A and B (A * B) is a set that contains elements common to both A and B. The difference of two sets A and B (A - B) is a set that contains only the elements which are in A but not in B. For example, if A and B are two sets of integers defined as A = { 5, 7, 8, 10 } and B = { 3, 9, 10 }, then their union (A + B) is the set { 3, 5, 7, 8, 9, 10 } their intersection (A * B) is the set { 10 } the difference of A and B (A - B) is the set { 5, 7, 8 } the difference of B and A (B - A) is the set { 3, 9 }. Input File File setdata.txt contains an even number of lines of data. Each line represents the values to be assigned to a set. Each line contains up to 25 random positive integers with a space between consecutive integers. The integers are in no particular order, and a particular integer may appear more than once. Example: 4 8 10 2 14 7 10 8 Processing Write a program that repeats the following until end of file: 1) Read a line of data and store the input integers in set (array) A. Read another line of data and store the integers in set (array) B. Echo print both input sets. 2) Make sure that both arrays contain proper sets by eliminating duplicate values in each. Place set values in ascending order (while the order of set values is immaterial, the set is easier to read and more efficient to check if its values are in order, and it gives me an excuse to ask you to use a sort). You will probably find it easier to eliminate duplicates if you do the sort first. 3) Compute and print the union of A and B (A + B), the intersection of A and B (A * B), the difference of A and B (A - B), and the difference of B and A (B - A). Example of the output format required: A = { 3 1 2 4} B = { 8 4 6 5 3 6 4 } { 1 2 3 4 } + { 3 4 5 6 8 } = { 1 2 3 4 5 6 8 } { 1 2 3 4 } * { 3 4 5 6 8 } = { 3 4 } { 1 2 3 4 } - { 3 4 5 6 8 } = { 1 2 } { 3 4 5 6 8 } - { 1 2 3 4 } = { 5 6 8 } Program Requirements: 1) Since the purpose of this assignment is to give you practice in array manipulations and in sorting and searching, YOU MAY NOT USE the Standard Template set type or other predefined set functions. 2) You must call a sort function to sort each set. You may use either the bubble sort or the selection sort from the book to implement sorting. You could also use your bucket sort you developed for Assignment #2 as your sorting method. 3) You may assume that the data will be valid positive integers. 4) The set unions which you calculate should not contain any duplicate values. You might find it useful to have a function which eliminates duplicates. You could call it for your input sets as well as for the set union calculated. 5) The union, intersection, and difference operations should be implemented as functions to make it easier to use them in other applications where a set might be useful. 6) All union, intersection, and difference sets should be shown with values in ascending order (call your sort function again). 7) Sets should be output as shown in the examples (values printed with a space or a comma between consecutive values and enclosed in curly braces). SAMPLE DATA FILE: 15 13 7 5 2 15 6 6 12 13 12 8 8 9 11 11 1 8 9 4 15 2 3 11 9 12 9 4 6 11 10 13 12 8 9 8 15 4 15 8 15 5 13 2 6 13 12 7 7 12 1 14 9 11 4 6 3 5 4 6 10 4 15 2 7 5 10 1 8 9 3 2 2 4 10 1 6 8 9 8 5 5 1 6 8 12 9 5 14 13 7 10 4 15 5 4 4 3 2 4 1 15 8 2 4 15 14 15 9 7 10 15 1 12 3 9 12 12 2 7 9 7 5 14 13 1 1 11 12 6 15 5 4 8 14 13 7 EXAMPLE RESULTS ON SAMPLE DATA FILE: A = { 15 13 7 5 2 15 } A = { 2 5 7 13 15 } B = { 6 6 12 13 12 8 8 9 11 11 1 8 9 4 15 2 3 11 } B = { 1 2 3 4 6 8 9 11 12 13 15 } { 2 5 7 13 15 } + { 1 2 3 4 6 8 9 11 12 13 15 } = { 1 2 3 4 5 6 7 8 9 11 12 13 15 } { 2 5 7 13 15 } * { 1 2 3 4 6 8 9 11 12 13 15 } = { 2 13 15 } { 2 5 7 13 15 } - { 1 2 3 4 6 8 9 11 12 13 15 } = { 5 7 } { 1 2 3 4 6 8 9 11 12 13 15 } - { 2 5 7 13 15 } = { 1 3 4 6 8 9 11 12 } A = { 9 12 9 4 6 11 10 13 12 8 9 8 15 4 15 8 15 5 13 2 6 13 12 } A = { 2 4 5 6 8 9 10 11 12 13 15 } B = { 7 7 12 1 14 9 11 4 6 3 5 4 6 10 4 15 2 7 5 10 1 } B = { 1 2 3 4 5 6 7 9 10 11 12 14 15 } { 2 4 5 6 8 9 10 11 12 13 15 } + { 1 2 3 4 5 6 7 9 10 11 12 14 15 } = { 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 } { 2 4 5 6 8 9 10 11 12 13 15 } * { 1 2 3 4 5 6 7 9 10 11 12 14 15 } = { 2 4 5 6 9 10 11 12 15 } { 2 4 5 6 8 9 10 11 12 13 15 } - { 1 2 3 4 5 6 7 9 10 11 12 14 15 } = { 8 13 } { 1 2 3 4 5 6 7 9 10 11 12 14 15 } - { 2 4 5 6 8 9 10 11 12 13 15 } = { 1 3 7 14 } A = { 8 } A = { 8 } B = { 9 3 2 2 4 } B = { 2 3 4 9 } { 8 } + { 2 3 4 9 } = { 2 3 4 8 9 } { 8 } * { 2 3 4 9 } = { } { 8 } - { 2 3 4 9 } = { 8 } { 2 3 4 9 } - { 8 } = { 2 3 4 9 } A = { 10 1 6 8 9 8 5 5 1 6 8 12 9 5 14 } A = { 1 5 6 8 9 10 12 14 } B = { 13 7 10 4 15 5 4 4 3 2 4 1 15 8 2 4 15 14 15 9 7 10 15 1 12 } B = { 1 2 3 4 5 7 8 9 10 12 13 14 15 } { 1 5 6 8 9 10 12 14 } + { 1 2 3 4 5 7 8 9 10 12 13 14 15 } = { 1 2 3 4 5 6 7 8 9 10 12 13 14 15 } { 1 5 6 8 9 10 12 14 } * { 1 2 3 4 5 7 8 9 10 12 13 14 15 } = { 1 5 8 9 10 12 14 } { 1 5 6 8 9 10 12 14 } - { 1 2 3 4 5 7 8 9 10 12 13 14 15 } = { 6 } { 1 2 3 4 5 7 8 9 10 12 13 14 15 } - { 1 5 6 8 9 10 12 14 } = { 2 3 4 7 13 15 } A = { 3 9 12 } A = { 3 9 12 } B = { 12 2 7 9 7 5 14 13 1 1 11 12 6 15 5 4 8 14 13 7 } B = { 1 2 4 5 6 7 8 9 11 12 13 14 15 } { 3 9 12 } + { 1 2 4 5 6 7 8 9 11 12 13 14 15 } = { 1 2 3 4 5 6 7 8 9 11 12 13 14 15 } { 3 9 12 } * { 1 2 4 5 6 7 8 9 11 12 13 14 15 } = { 9 12 } { 3 9 12 } - { 1 2 4 5 6 7 8 9 11 12 13 14 15 } = { 3 } { 1 2 4 5 6 7 8 9 11 12 13 14 15 } - { 3 9 12 } = { 1 2 4 5 6 7 8 11 13 14 15 } I hope this is enough info. I need this by SAT. night 3-19-05. If anyone can help I would appreciate it.

• Answer:

  Hi, OK, I assume selectionsort and give you that for free. Enclosed are 3 files-- put them in the same directory: set.cpp - main program utils.hh - helper functions to parse input file and do sorting input.txt - input file Compile just set.cpp. Run set.exe and the output is as shown (see below). Compile.log from Dev C++ is also enclosed. ================================================================================ set.cpp: ================================================================================ #include <string> #include <iostream> #include <fstream> #include <vector> #include "utils.hh" using namespace std; int main() { ifstream in("input.txt"); if (!in) return EXIT_FAILURE; int t[25]; int a[25]; int b[25]; int u[50]; //union int x[25]; //intersection int d[25]; //difference string line; StringArray &tokens = * new StringArray(""); while (getline(in,line)) { size_t sz_t=0, sz_a=0, sz_b=0, sz_u=0, sz_x=0, sz_d=0; cout << "from file: " << line << endl; tokens = * new StringArray(line); for (int i=0; i<tokens.size(); ++i) { t[i] = atoi(tokens.at(i).c_str()); ++sz_t; } //sort t[sz_t] selectsort(t, sz_t); //make unique for (int i=0; i<sz_t; ++i) { bool found=false; for(int j=0; j<sz_a; ++j) { if (t[i] == a[j]) { found = true; break; } } if (!found) { a[sz_a] = t[i]; ++sz_a; } } cout << "A = { "; for(int i=0; i<sz_a; ++i) { cout << a[i] << " "; } cout << "}" << endl; sz_t=0; getline(in,line); cout << "from file: " << line << endl; tokens = * new StringArray(line); for (int i=0; i<tokens.size(); ++i) { t[i] = atoi(tokens.at(i).c_str()); ++sz_t; } //sort t[sz_t] selectsort(t, sz_t); //make unique for (int i=0; i<sz_t; ++i) { bool found=false; for(int j=0; j<sz_b; ++j) { if (t[i] == b[j]) { found = true; break; } } if (!found) { b[sz_b] = t[i]; ++sz_b; } } cout << "B = { "; for(int i=0; i<sz_b; ++i) { cout << b[i] << " "; } cout << "}" << endl; //compute union for(int i=0; i<sz_a; ++i) { u[i] = a[i]; ++sz_u; } int sz_u_old = sz_u; for(int i=0; i<sz_b; ++i) { bool found=false; for(int j=0; j<sz_u_old; ++j) { if (b[i] == u[j]) { found = true; break; } } if (!found) { u[sz_u] = b[i]; ++sz_u; } } //sort u[sz_u] selectsort(u, sz_u); cout << "A + B = { "; for(int i=0; i<sz_u; ++i) { cout << u[i] << " "; } cout << "}" << endl; //compute intersection for(int i=0; i<sz_a; ++i) { for(int j=0; j<sz_b; ++j) { if (a[i] == b[j]) { x[sz_x] = a[i]; ++sz_x; } } } //sort x[sz_x] selectsort(x, sz_x); cout << "A * B = { "; for(int i=0; i<sz_x; ++i) { cout << x[i] << " "; } cout << "}" << endl; //compute differences //A - B for(int i=0; i<sz_a; ++i) { bool found=false; for(int j=0; j<sz_b; ++j) { if (a[i] == b[j]) { found = true; break; } } if (!found) { d[sz_d] = a[i]; ++sz_d; } } //sort d[sz_d] selectsort(d, sz_d); cout << "A - B = { "; for(int i=0; i<sz_d; ++i) { cout << d[i] << " "; } cout << "}" << endl; sz_d = 0; //B - A for(int i=0; i<sz_b; ++i) { bool found=false; for(int j=0; j<sz_a; ++j) { if (b[i] == a[j]) { found = true; break; } } if (!found) { d[sz_d] = b[i]; ++sz_d; } } //sort d[sz_d] selectsort(d, sz_d); cout << "B - A = { "; for(int i=0; i<sz_d; ++i) { cout << d[i] << " "; } cout << "}" << endl; //final cout << endl; } return 0; } ================================================================================ utils.hh: ================================================================================ #include <vector> #include <string> using namespace std; using namespace std; class StringArray { public: protected: vector<string> rep; public: StringArray(void); StringArray(const string & s); virtual ~StringArray(void); int size(void); void add(const string & s); const string & at(int index); void tokenize(const string & t); }; StringArray::StringArray(void) { } StringArray::~StringArray() { } int StringArray::size(void) { return (int)rep.size(); } void StringArray::add(const string & s) { rep.push_back(s); } const string & StringArray::at(int index) { return rep.at(index); } StringArray::StringArray(const string & s) { tokenize(s); } void StringArray::tokenize(const string & t) { string s = t + " "; int i = 0; char ch = s.at(i++); while (true) { while (isspace(ch)) { if (i == s.length()) return; ch = s.at(i++); } int start = i-1; if (ch == '"') { if (i == s.length()) return; ch = s.at(i++); while (ch != '"') { if (i == s.length()) { return; } ch = s.at(i++); } add(s.substr(start+1, i - start - 2)); } else { while (!isspace(ch)) { if (i == s.length()) { break; } ch = s.at(i++); } add(s.substr(start,i-start-1)); } if (i == s.length()) return; } } void selectsort (int arr[], int size) //selection sort { int i_of_min; int pass; int j; for (pass=0; pass<size-1; pass++) { i_of_min = pass; for (j=pass+1; j<size; j++) if (arr[j]<arr[pass]) i_of_min = j; swap (arr[pass], arr[i_of_min]); } } // swap function for integers void swap (int &x, int &y) { int temp; temp = x; x = y; y = temp; } ================================================================================ input.txt: ================================================================================ 2 1 2 3 4 5 4 6 6 6 8 7 7 8 9 ================================================================================ output: ================================================================================ from file: 2 1 2 3 A = { 1 2 3 } from file: 4 5 4 B = { 4 5 } A + B = { 1 2 3 4 5 } A * B = { } A - B = { 1 2 3 } B - A = { 4 5 } from file: 6 6 6 8 7 7 A = { 6 7 8 } from file: 8 9 B = { 8 9 } A + B = { 6 7 8 9 } A * B = { 8 } A - B = { 6 7 } B - A = { 9 } ================================================================================ compile.log: ================================================================================ Compiler: Default compiler Executing g++.exe... g++.exe "P:\.mill\set.cpp" -o "P:\.mill\set.exe" -I"E:\Dev-Cpp\lib\gcc\mingw32\3.4.2\include" -I"E:\Dev-Cpp\include\c++\3.4.2\backward" -I"E:\Dev-Cpp\include\c++\3.4.2\mingw32" -I"E:\Dev-Cpp\include\c++\3.4.2" -I"E:\Dev-Cpp\include" -L"E:\Dev-Cpp\lib" Execution terminated Compilation successful