조합 관련 질문

{ 
 { 1 2 3 4 5 6 } 
 { 1 2 3 4 5 7 } 
 { 1 2 3 4 5 8 } 
 { 1 2 3 4 6 7 } 
 { 1 2 3 4 6 8 } 
 { 1 2 3 4 7 8 } 
 { 1 2 5 6 7 8 } 
 { 1 3 5 6 7 8 } 
 { 1 4 5 6 7 8 } 
 { 2 3 5 6 7 8 } 
 { 2 4 5 6 7 8 } 
 { 3 4 5 6 7 8 }
}

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// Types
typedef set<int>                                SetGenerator;
typedef set<int>::iterator                      SetGeneratorIt;
typedef set<SetGenerator>                       Set;
typedef set<SetGenerator>::iterator             SetIt;
typedef set<Set>                                ResultSet;
typedef set<Set>::iterator                      ResultSetIt;
 
// Display class
class CDisplay
{
public:
    static void DisplaySet(const Set &s);
    static void DisplayAll(const ResultSet &rs);
};
 
void CDisplay::DisplaySet(const Set &s)
{
    SetIt sit;
    SetGeneratorIt sgit;
 
    cout << "{ ";
    for( sit = s.begin(); sit != s.end(); sit++ )
    {
        cout << "{ ";
        for( sgit = sit->begin(); sgit != sit->end(); sgit++ )
            cout << *sgit << " ";
        cout << "} ";
    }
    cout << "}" << endl;
}
 
void CDisplay::DisplayAll(const ResultSet &rs)
{
    ResultSetIt rsit;
 
    for( rsit = rs.begin(); rsit != rs.end(); rsit++ )
        DisplaySet(*rsit);
}
 
// Combination generator class
class CCombination
{
public:
    inline CCombination(int n, int r) { SetGenerator s; Generate(s, n, r); };
 
    inline Set &GetResult(void) { return mySet; };
 
private:
    Set mySet;
 
    void Generate(SetGenerator s, int n, int r);
};
 
void CCombination::Generate(SetGenerator s, int n, int r)
{
    if( r == 0 )
    {
        if( mySet.find(s) == mySet.end() )
            mySet.insert(s);
 
        return;
    }
 
    for( int i = 1; i <= n; i++ )
    {
        if( s.find(i) == s.end() )
        {
            s.insert(i);
            Generate(s, n, r - 1);
            s.erase(i);
        }
    }
}
 
// Comparison class
class CCompareSet
{
public:
    static bool IsSubSet(const SetGenerator &orig, const SetGenerator &comp);
    static ResultSet GetMinimalSet(const Set &orig, const Set &comp);
 
private:
    static void InnerComparator(ResultSet &s, Set cs, const Set &orig, const Set &comp);
};
 
bool CCompareSet::IsSubSet(const SetGenerator &orig, const SetGenerator &comp)
{
    if( orig.size() < comp.size() )
        return false;
 
    for( SetGeneratorIt it = comp.begin(); it != comp.end(); it++ )
    {
        if( orig.find(*it) == orig.end() )
            return false;
    }
 
    return true;
}
 
// Greedy algorithm
void CCompareSet::InnerComparator(ResultSet &s, Set cs, const Set &orig, const Set &comp)
{
    int s1, s2;
    SetIt it, it2;
    vector<SetGenerator> eraseList;
    vector<SetGenerator>::iterator vit;
    Set o, o2, c;
 
    if( comp.empty() )
    {
        s1 = cs.size();
 
        if( s.begin() == s.end() )
            s2 = 0x7fffffff;
        else
            s2 = s.begin()->size();
 
        if( s1 > s2 )
            return;
 
        if( s1 < s2 )
            s.clear();
 
        s.insert(cs);
 
        // this result can be updated during calculation
        cout << "Interim sets: " << endl;
        CDisplay::DisplayAll(s);
 
        return;
    }
 
    s2 = 0;
    o.clear();
    for( it = orig.begin(); it != orig.end(); it++ )
    {
        for( s1 = 0, it2 = comp.begin(); it2 != comp.end(); it2++ )
        {
            if( IsSubSet(*it, *it2) )
                s1++;
        }
 
        if( s1 < s2 )
            continue;
 
        if( s1 > s2 )
            o.clear();
 
        o.insert(*it);
        s2 = s1;
    }
 
    for( it = o.begin(); it != o.end(); it++)
    {
        o2 = orig;
        o2.erase(*it);
        cs.insert(*it);
 
        c = comp;
        eraseList.clear();
        for( it2 = comp.begin(); it2 != comp.end(); it2++ )
        {
            if( IsSubSet(*it, *it2) )
                eraseList.push_back(*it2);
        }
 
        for( vit = eraseList.begin(); vit != eraseList.end(); vit++)
                c.erase(*vit);
 
        InnerComparator(s, cs, o2, c);
 
        cs.erase(*it);
    }
}
 
ResultSet CCompareSet::GetMinimalSet(const Set &orig, const Set &comp)
{
    Set currentSet;
    ResultSet minimalSet;
 
    InnerComparator(minimalSet, currentSet, orig, comp);
 
    return minimalSet;
}
 
// Main
int main(void)
{
    CCombination c1(8,6), c2(8,5); // two nCr value sets
    ResultSet rs;
 
    // calcuate minimal set
    rs = CCompareSet::GetMinimalSet(c1.GetResult(), c2.GetResult());
 
    // final result
    cout << "Result: " << endl;
    CDisplay::DisplayAll(rs);
 
    return 0;
}