/* Warm - up Problem 0B: Random Subsets
There are 2^n possible subsets of a set of n elements
(Two possibilities for each of the n members : in or out).
That's growing exponentially, so it can take a very long time print
them to a list.  What if instead of generating all possible subsets,
we just generate a few random subsets?  That way, we can get a rough
sense for what the subsets look like.

To generate a random subset from a set we visit every element of the set,
one after the other, and flip a fair coin to decide whether or not to
include that element in the resulting subset.

As long as the coin tosses are fair, this produces a uniformly -
random subset of the given set.

Write a function

set<int> randomSubsetOf(set<int>& s);

that accepts as input a set<int> and returns a random subset of that set.
Your algorithm should be recursive and not use any loops(for, while, etc.)

Strategy:

Generating Subsets
? The only subset of an empty set is the
empty set itself.
? Otherwise:
? Fix some element x of the set.
? Generate all subsets of the set formed by
removing x from the main set.
? These subsets are subsets of the original set.
? All of the sets formed by adding x into those
subsets are subsets of the original set.

Suppose you start with three element, say { A, H, I }
This set is not empty (the base case) so we remove A and
make a second call to subSetsOf on { H, I } (the first call
to subSetsOf is now placed on the stack of function calls
and is yet to be resolved.)
Now { H, I } is not empty so remove H and call subSetsOf
on { I } (we now have three function calls pending on the stack.)
The set is still not empty so we remove I and make a fourth call
to subSetsOf, this time on an empty set...the base case:

{ A, H, I }
{ H, I }
{ I }
{ } ---> this lass call returns { }, and
the empty set is pushed on our vector, results.
This means the pending call before this last call
can be resolved and we have
{ A, H, I }
{ H, I }
{ I } ---> pushed on results: {I}, { }
{ }   ---> results became { }

{ A, H, I }
{ H, I } ---> now we get {H, I}, {H}, {I}, { }
{ I } ---> then results became {I}, { }
{ }   ---> results became { }

{ A, H, I } ---> Finally {A, H, I}, {A, H}, {A, I}, {A}, {H, I}, {H}, {I}, { }
{ H, I } ---> then {H, I}, {H}, {I}, { }
{ I } ---> then results became {I}, { }
{ }   ---> results became { }*/

#include <set>
using std::set;
#include <iostream>
using std::cin;
using std::cout;
#include <random>
#include <vector>
using std::vector;
#include <string>
using std::string;
#include <io.h>
#include <fcntl.h>

std::random_device random_device;
std::mt19937 random_engine{ random_device() };
std::bernoulli_distribution coin_distribution{ 0.5 };

vector< set<int> > subsetsOf(set<int>& s);
set<int> randomSubsetOf(set<int>& s);

vector< set<string> > subsetsOfS(set<string>& s);
set<string> randomSubsetOfS(set<string>& s);

int main() {
	char ans1, ans2;
	for (int i = 1; i < 6; ++i) cout << char(i);
	int ints[] = { 10,20,30,40,50 };
	string cards[] = { "AC", "2C", "3C", "4C", "5C", "6C", "7C",
		"8C", "9C", "10C", "JC", "QC", "KC", "AD", "2D", "3D", "4D", "5D", "6D", "7D",
		"8D", "9D", "10D", "JD", "QD", "KD", "AH", "2H", "3H", "4H", "5H", "6H", "7H",
		"8H", "9H", "10H", "JH", "QH", "KH", "AS", "2S", "3S", "4S", "5S", "6S", "7S",
		"8S", "9S", "10S", "JS", "QS", "KS" };
	set<int> values(ints, ints + 5);
	set<string> cardz(cards, cards + 52);
	while (1) {
		cout << "Do you want values or cardz? (v or c):\n";
		cin >> ans1;
		cout << "Enter A to find all subsets, or R to find a random subset:'\n'";
		cin >> ans2;
		if (toupper(ans1) == 'V' && toupper(ans2) == 'A')
			for (set<int> subset : subsetsOf(values)) {
				for (int i : subset) {
					cout << i << " ";
				}
				cout << '\n';
			}
		else if (toupper(ans1) == 'V' && toupper(ans2) == 'R') {
			cout << "Here are 5 random subsets:\n";
			for (int j = 0; j < 5; ++j) {
				for (int i : randomSubsetOf(values))
					cout << i << " ";
				cout << '\n';
			}
		}
		else if (toupper(ans1) == 'C' && toupper(ans2) == 'A')
			for (set<string> subset : subsetsOfS(cardz)) {
				for (string str : subset) {
					cout << str << " ";
				}
				cout << '\n';
			}
		else if (toupper(ans1) == 'C' && toupper(ans2) == 'R') {
			cout << "Here are 5 random subsets:\n";
			for (int j = 0; j < 5; ++j) {
				for (string str : randomSubsetOfS(cardz))
					cout << str << " ";
				cout << '\n';
			}
		}
		cin.ignore();
		cin.get();
	}
}

vector< set<int> > subsetsOf(set<int>& s) {

	if (s.empty()) { //base case
		vector< set<int> > result;
		result.push_back(s);
		return result;
	}
	else {
		set<int>::iterator itr = s.begin();
		int elem = *itr;
		s.erase(elem);
		set<int> rest = s;
		vector< set<int> > result;
		for (set<int> s : subsetsOf(rest)) {
			result.push_back(s);
			s.insert(elem);
			result.push_back(s);
		}
		return result;
	}
}

void randomSubsetRec(set<int>& input, set<int>& output, set<int>::iterator itr) {
	if (itr == input.end()) return; // base case
	if (coin_distribution(random_engine)) {
		output.insert(*itr);
		//cout << *itr << " ";
	}
	randomSubsetRec(input, output, ++itr);
}

set<int> randomSubsetOf(set<int>& s) {
	set<int> output;
	randomSubsetRec(s, output, s.begin());
	return output;
}

/// string versions
vector< set<string> > subsetsOfS(set<string>& s) {


	if (s.empty()) { //base case
		vector< set<string> > result;
		result.push_back(s);
		return result;
	}
	else {
		set<string>::iterator itr = s.begin();
		string elem = *itr;
		s.erase(elem);
		set<string> rest = s;
		vector< set<string> > result;
		for (set<string> s : subsetsOfS(rest)) {
			result.push_back(s);
			s.insert(elem);
			result.push_back(s);
		}
		return result;
	}
}

void randomSubsetRecS(set<string>& input, set<string>& output, set<string>::iterator itr) {
	if (itr == input.end()) return; // base case
	if (coin_distribution(random_engine)) {
		output.insert(*itr);
		//cout << *itr << " ";
	}
	randomSubsetRecS(input, output, ++itr);
}

set<string> randomSubsetOfS(set<string>& s) {
	set<string> output;
	randomSubsetRecS(s, output, s.begin());
	return output;
}