/*
 * This code demonstrates 2 techniques for finding all 
 * subsets of a given set: the backtracking algorithm heuristic
 * and a technique based on binary couting.  It also illustrates
 * the backtracking heuristic to find all permutations.
 */
#include <iostream>
#include <vector>
#include <set>
#include <bitset>
#include <stl_algobase.h> //fix for bitset error in gcc
#include <math.h>
#include <algorithm>

//find all subsets using backtracking technique
void backTracking()
{
    //size of set to find all subsets of
    const int n = 15;
    //bit vector whose position indicates
    //whether or not the element at index
    //is present for a given subset
    vector<bool> A;
    
    //put n+1 boolean slots into A
    //(don't use index 0)
    for(int i=0; i<=n; i++)
    {
        A.push_back(false);
    }
    
    //create initial set of all possibilities
    set<bool> S;
    S.insert(true);
    S.insert(false);
    
    //create vector of Sets of to remember S
    //for each k
    vector< set<bool> > Ses;
    //put n sets of all initial possibilities
    //for each k in Ses
    //(**don't use index 0)
    for(int i=0; i<=n; i++)
    {
        Ses.push_back(S);
    }
    
    //create empty set
    S.clear();
    //make Ses[n+1] = empty set because
    //there are no legal values for 
    //that position
    Ses.push_back(S);
    
    int k=1;
    bool ak = false;
    
    while(k > 0)
    {
        while(!Ses[k].empty())
        {
            ak = *(--Ses[k].end());
            Ses[k].erase(ak);
            A[k] = ak;
            
            if(k == n)
            {
                cout << "{";
                for(int i=1; i<=k; i++)
                {
                    //if(bits[j])
                    //  cout << candidates[j] << " ";
                    cout << A[i] << " ";
                }
                cout << "\b}" << endl;
            }
            k++;
            //if this new k is legal
            //and S[k] is empty, refill it
            //i.e. if there is a legal way to extend
            //the partial solution, enumerate
            //the possibilities
            if(k <= n && Ses[k].empty())
            {
                Ses[k].insert(true);
                Ses[k].insert(false);
            }
        }
        k--; //backtrack
    }
}

//find all permutations using backtracking technique
//beware, there are n! permutations for n
void backTracking2()
{
    int num = 0;
    
    //size of set to find all subsets of
    const int n = 3;
    //int vector whose position value 
    //stores the value for each permutation
    vector<int> A;
    
    //put n+1 int slots into A
    //(don't use index 0)
    for(int i=0; i<=n; i++)
    {
        A.push_back(0);
    }
    
    set<int> Aset;
    //track which elements are in each A
    vector<set<int> > As;
    
    for(int i=0; i<=n; i++)
    {
        As.push_back(Aset);
    }
    
    //create initial set of all possibilities
    set<int> S;
    for(int i=1; i<=n; i++)
        S.insert(i);
    
    //create vector of Sets of to remember S
    //for each k
    vector< set<int> > Ses;
    //put n sets of all initial possibilities
    //for each k in Ses
    Ses.push_back(S); // (**don't use index 0)
    for(int i=1; i<=n; i++)
    {
        Ses.push_back(S);
        S.erase(*(--S.end()));
    }
    
    //Ses[n+1] = empty set because
    //there are no legal values for 
    //that position
    Ses.push_back(S);
    
    int k=1;
    int ak = -1;
    
    set<int> tempSet;
    
    while(k > 0)
    {
        while(!Ses[k].empty())
        {
            ak = *(Ses[k].begin());
            Ses[k].erase(ak);
            A[k] = ak;
            As[k] = As[k-1];
            As[k].insert(ak);
            
            if(k == n)
            {
                num++;
                
                cout << "{";
                for(int i=1; i<=k; i++)
                {
                    cout << A[i] << " ";
                }
                cout << "\b}" << endl;
            }
            k++;
            //if there is a legal way to extend
            //the partial solution, enumerate
            //the possibilities by updating the
            //current Ses[k] which is the symmetric
            //set difference of Ses[k] and As[k-1]
            if(k <= n)
            {
                //enumerate all possible values
                for(int i=1; i<=n; i++)
                    Ses[k].insert(i);
                tempSet.clear();
                //remove values present in previous
                //partial solution
                set_symmetric_difference(As[k-1].begin(), As[k-1].end(),
                               Ses[k].begin(), Ses[k].end(),
                               insert_iterator<set<int> >(tempSet, tempSet.begin()));
                Ses[k].clear();
                Ses[k] = tempSet;   
            }
        }
        k--; //backtrack
        //keep As[k] in sync with A
        As[k].erase(A[k]);
    }

    cout << "num permutations=" << num << endl;
}

//find all subsets using binary counting technique
void binaryCounting()
{
    //Create all subsets via binary counting technique
    //set size to do subsets of
    const int n = 15;
    int candidates[n];
    //fill set with 1..n
    for(int i=1; i<=n; i++)
        candidates[i-1]=i;
    bitset<n> bits;
    vector<int> S(candidates, candidates+n);
    
    for(int i=0; i<(pow(2,n)); i++)
    {
        //cout << (bits = i) << endl;
        bits = i;
        cout << "{";
        
        for(int j=0; j<n; j++)
        {
            //if(bits[j])
            //  cout << candidates[j] << " ";
            cout << bits[j] << " ";
        }

        //if(i!=0)
            cout << "\b";
        cout << "}" << endl;
    }
    
}

int main()
{
    //backTracking();
    //binaryCounting();
    
    backTracking2();
    return 0;
}