# Quine-McCluskey
I hate this.cpp:

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <set>
#include <bitset>
using namespace std;
int n;
void generateNumbers(const string& input, vector<int>& output)
{
    int count = 0;
    for (char ch:input)
        if (ch == '-') count++;
    int poss = pow(2, count);
    for (int i=0; i<poss; i++)
	{
        string binary = bitset<32>(i).to_string().substr(32 - count);
        string result = input;
        int binaryIndex = 0;
        for (char& ch:result)
		{
            if (ch == '-')
			{
                ch = binary[binaryIndex];
                binaryIndex++;
            }
        }
        output.push_back(std::stoi(result, nullptr, 2));
    }
}
bool cmp2(string a, string b) // hard to identify whether the answer is correct, not necessary
{
    int size = min(a.size(), b.size());
    for (int i = 0; i < size; i++)
    {
        if (a[i] != b[i])
        {
            if (a[i] == '\'') return false;
            if (b[i] == '\'') return true;
            return a[i] < b[i];
        }
    }
    return a.size() < b.size();
}

bool cmp(string a, string b) // sort the list, but kinda useless
{
    int cnta = count(a.begin(), a.end(), '1');
    int cntb = count(b.begin(), b.end(), '1');
    if (cnta != cntb)
        return cnta < cntb;
    return a < b;
}

string toBinary(string enter) // convert number to binary form
{
	string binary;
	int cur = stoi(enter);
	while(cur)
	{
		binary += to_string(cur%2);
		cur/=2;
	}
	while(binary.size()!=n)
	{
		binary += "0";
	}
	reverse(binary.begin(),binary.end());
	//cout << binary << endl;
	return binary;
}
int main(void)
{
	bool DontCare = false;
	string enter;
	cout << "Please Enter varible amount: ";
	cin >> n;
	vector<string> minterm, table, temp;
	set<string> res;
	cin.ignore();
	cout << "Please Enter minterm: ";
	getline(cin,enter);
	stringstream ss(enter);
	while(ss >> enter)
	{
		if(enter == "d") DontCare = true; // dontcare's switch on
		else if(DontCare == true)
		{
			minterm.push_back(toBinary(enter));
		}
		else
		{
			minterm.push_back(toBinary(enter));
			table.push_back(enter); // for prime implicant table
		}
	}
	sort(minterm.begin(), minterm.end(),cmp);
	
	int Mergetime = -1;
	while(Mergetime != 0) // find prime implicant
	{
		Mergetime = 0;
		vector<bool> usedlist(minterm.size(), false);
		for(int i=0;i<minterm.size();i++)
		{
			for(int j=i+1;j<minterm.size();j++)
			{
				int diff = 0;
				string cur = minterm[i];
				for(int index=0;index<n;index++)
				{
					//cout << minterm[i][index] << " vs " << minterm[i][index]
					if(minterm[i][index] != minterm[j][index])
					{
						diff++;
						cur[index] = '-';
					}
					if(diff >= 2) break;
				}
				if(diff == 1) 
				{
					usedlist[i] = usedlist[j]= true;
					//cout << "Merge!!!" << endl;
					//cout << cur << endl;
					Mergetime++;
					temp.push_back(cur);
				}
			}
		}
		for(int check = 0;check < usedlist.size();check++)
		{
			if(usedlist[check] == false)
				res.insert(minterm[check]);	
		}
		//for(auto cur: usedlist) cout << cur << endl;
		//for(auto cur: temp) cout << cur << endl;
		minterm.clear();
		for(auto cur: temp) minterm.push_back(cur);
		temp.clear(); 
	}
	/*
	for(auto it = res.begin();it != res.end();it++)
	{
		cout << *it << endl;
	}
	*/
	vector<vector<bool>> list(res.size(),vector<bool>(table.size(),0));
	int cnt = 0;
	for(auto it=res.begin();it!=res.end();it++,cnt++)
	{
		string cur = *it;
		//cout << "cur: " << cur << "  ";
		vector<int> output;
		generateNumbers(cur, output);
		//for(int i=0;i<output.size();i++) cout << to_string(output[i]) << endl;
		//for(int j=0;j<table.size();j++) cout << table[j] << endl;
		for(int i=0;i<output.size();i++)
		{
			for(int j=0;j<table.size();j++)
			{
				if(to_string(output[i]) == table[j])
				{
					list[cnt][j] = true;
				}
			}
		}
		output.clear();
	}
	/*
	cout << "Before:\n";
	for(int i=0;i<res.size();i++)
	{
	    for(int j=0;j<table.size();j++)
		{
			if(list[i][j])
			{
				cout << "X" << " ";
			}
	        else cout << list[i][j] << " ";
	    }
	    cout << endl;
	}
	*/
	vector<int> spot;
	for(int i=0;i<list[0].size();i++)
	{
		int c=0;
		for(int j=0;j<list.size();j++)
		{
			if(list[j][i] == 1) c++;
		}
		if(c == 1)
		{
			for(int x=0;x<list.size();x++)
			{
				if(list[x][i] == 1) // find the one in the count list
				{
					spot.push_back(x); 
					for(int y=0;y<list[0].size();y++) // delete the column that this one include
					{
						if(list[x][y] == 1) // if included
						{
							for(int reset=0;reset<list.size();reset++)
							{
								if(y != i)
									list[reset][y] = false;
							}
						}
					}
				}
			}
			for(int reset = 0;reset<list.size();reset++) // must be the last one deleted
			{
				list[reset][i] = false;
			}
		}
	}
	
	cout << "Essential Prime Implicant: " << endl;
	if(!spot.empty())
	{
		sort(spot.begin(),spot.end());	
		int x = 0,y = 0;
		vector<string> sortedans;
		for(auto it = res.begin();it != res.end();it++,x++)
		{
			string cur = *it;
			//cout << "x = " << x << ", cur = " << cur << endl;
			if(x == spot[y])
			{
				//cout << "x = " << x << ", getting spot" << endl;
				y++;
				string ans;
				for(int i=0;i<n;i++)
				{
					if(cur[i] != '-')ans+=char('a'+i);//cout << char('a'+i);
					if(cur[i] == '0') ans+="\'";//cout << "\'";
				}
				if (ans.empty()) ans = "1";
				sortedans.push_back(ans);
			}
		}
		sort(sortedans.begin(),sortedans.end(),cmp2);
		for(auto cur: sortedans) cout << cur << ", "[cur == sortedans[sortedans.size()-1]];
		cout << endl;
	}
	else cout << "None" << endl;

	
	
	bool stop = false;
	int round = 1;
	vector<int> spot2;
	while(!stop)
	{
		round++;
		//cout << "Round = " << round << endl;
		//cout << endl;
		int mx = 0;
		for(int i=0;i<list.size();i++) // = res.size()
		{
			int c=0;
			for(int j=0;j<list[0].size();j++)// = table.size()
			{
				if(list[i][j] == 1) c++;
			}
			if(c >= mx)
			{
				mx = max(mx,c);
				if(!spot2.empty()) spot2.pop_back();
				spot2.push_back(i);
			}
		}
		spot.push_back(spot2[0]);
		int i = spot2[spot2.size()-1];
		for(int j=0;j<list[0].size();j++)
		{
			if(list[i][j] == 1)
			{
				list[i][j] = 0;
				for(int x=0;x<list.size();x++)
				{
					list[x][j] = false;
				}
			}
		}
		stop = true;
		
		for(int i=0;i<res.size();i++)
		{
		    for(int j=0;j<table.size();j++)
			{
				if(list[i][j])
				{
					//cout << "X" << " ";
					stop = false;
				}
		        //else cout << list[i][j] << " ";
		    }
		    //cout << endl;
		}
		//cout << endl;
		if(round >= res.size()) stop = true;
		/*
			cout << "CurrentAns: " << endl;
		for(auto cur: spot) cout << cur << endl;
		for(auto cur: spot2) cout << cur << endl;
		*/
	}
	cout << "Ans: " << endl;
	sort(spot.begin(),spot.end());
	//for(auto cur: spot) cout << cur << endl;
	
	int x = 0,y = 0;
	vector<string> sortedans;
	for(auto it = res.begin();it != res.end();it++,x++)
	{
		string cur = *it;
		//cout << "x = " << x << ", cur = " << cur << endl;
		if(x == spot[y])
		{
			//cout << "x = " << x << ", getting spot" << endl;
			y++;
			string ans;
			for(int i=0;i<n;i++)
			{
				if(cur[i] != '-')ans+=char('a'+i);//cout << char('a'+i);
				if(cur[i] == '0') ans+="\'";//cout << "\'";
			}
			if (ans.empty()) ans = "1";
			sortedans.push_back(ans);
		}
	}
	sort(sortedans.begin(),sortedans.end(),cmp2);
	for(auto cur: sortedans) cout << cur << " + "[cur != sortedans[sortedans.size()-1]];
	
	//cout << endl;
	//for(auto cur: dontcare) cout << cur << endl;
}
/*
4
0 1 2 5 6 7 8 9 10 14
Essential Prime Implicant:
b'c',cd'
Ans:
a'bd+b'c'+cd'

3
0 1 2 5 6 7
Essential Prime Implicant:
None
Ans:
ab+ac+a'b'+a'c'(有三項的更簡解，但要使用 Petrick's Method)

4
2 3 7 9 11 13 d 1 10 15
Essential Prime Implicant:
ad,b'c,cd
Ans:
ad+b'c+cd

*/