питание Наборы ~ рекурсия ~ Хасса Диаграмма

Question

(СМ НИЖЕ ТАКЖЕ)

Так что у меня есть некоторые функции и некоторые операторы для телевизионной манипуляции программы я кодирование, и я хочу, чтобы иметь наборы питания как утилиты тоже (не считайте комментарии в коде). Я не хочу использовать двоичный подход, но хочу использовать рекурсию. Я видел в книге Ральфа Оберсте-Ворта Мост абстрактной математике определение наборов мощности (стр. 65), а на следующей странице я вижу все эти эквивалентности типа «если S = ​​X, то P (S) = P (X), "и" если A и B - множества, то P (A) UP (B) = P (AUB) ", и мне напомнили о рекурсии. Я думаю, что рекурсия может работать здесь, но я не уверен. Я играл с пакетом Combinatorica от Mathematica, а один Haverford College paper на диаграммах Hasse, и я думал, что смогу работать так же, как это делается here четыре минуты, какой-то метод, основанный на соответствующей диаграмме для некоторого набора размером n, но я не знаю, что это приведет меня к правильному пути. Я хотел бы построить свои уже построенные функции/операторы.

#include <iostream> 
#include <set> 
#include <ostream> 
#include <istream> 
#include <vector> 

using namespace std; 

set<int> SetUnion(set<int> A , set<int> B) // tus koj hlub 
{ 
    //A.insert(B.begin() , B.end()); 
    //return A; 

    set<int> pump; 
    for(set<int>::iterator cycle = A.begin() ; cycle != A.end() ; ++cycle) 
    { 
     pump.insert(*cycle); 
    } 
    for(set<int>::iterator cycle = B.begin() ; cycle != B.end() ; ++cycle) 
    { 
     pump.insert(*cycle); 
    } 
    return pump; 
} 

set<int> SetIntersection(set<int> A , set<int> B) // tus koj hlub 
{ 
    set<int> pump; 
    for(set<int>::iterator cycle = A.begin ; cycle != A.end() ; ++cycle) 
    { 
     if(B.find(*cycle) != B.end()) 
     { 
      pump.insert(*cycle); 
     } 
    } 
    return pump; 
} 

set<int> SetDifference(set<int> A , set<int> B) 
{ 
    set<int> pump; 
    for(set<int>::iterator cycle = A.begin ; cycle != A.end() ; ++cycle) 
    { 
     if(B.find(*cycle) == B.end()) 
     { 
      pump.insert(*cycle); 
     } 
    } 
    return pump; 
} 

set<int> SymmetricDifference(set<int> A , set<int> B) 
{ 
    return SetUnion(SetDifference(A , B) , SetDifference(B , A)); 
    //return SetDifference(SetUnion(A , B) , SetIntersection(A , B)); 
} 

set<set<int>> PowerSet(set<int> A) 
{ 
    /*statements*/ 
} 

set<int> Complement(set<int> A , int B) 
{ 
    set<int> pump; 
    for(int i = 1 ; i<=B ; i++) 
    { 
     pump.insert(i); 
    } 
    set<int> collect = SetDifference(A , pump); 
    return collect; 
} 

set<int> operator+(set<int> A , set<int> B) 
{ 
    return SetUnion(A, B); 
} 
set<int> operator+(set<int> A , int B) 
{ 
    set<int> C; 
    C.insert(B); 
    return SetUnion(A , C); 
} 
set<int> operator+(int A , set<int> B) 
{ 
    set<int> C; 
    C.insert(A); 
    return SetUnion(B , C); 
} 
set<int> operator-(set<int> A , set<int> B) 
{ 
    set<int> pump; 
    for(set<int>::iterator cycle = A.begin ; cycle != A.end() ; ++cycle) 
    { 
     if(B.find(*cycle) == B.end()) 
     { 
      pump.insert(*cycle); 
     } 
    } 
    return pump; 
} 
set<int> operator-(set<int> A , int B) 
{ 
    set<int> C; 
    C.insert(B); 
    set<int> pump = SetDifference(A , C); 
    return C; 
} 
set<int> operator-(int A , set<int> B) 
{ 
    set<int> C; 
    C.insert(A); 
    set<int> pump = SetDifference(B , C); 
    return pump; 
} 
set<int> operator^(set<int> A , set<int> B) 
{ 
    return SetUnion(A , B); 
} 
set<int> operator^(set<int> A , int B) 
{ 
    set<int> C; 
    C.insert(B); 
    set<int> pump = SetUnion(A , C); 
    return pump; 
} 
set<int> operator^(int A , set<int> B) 
{ 
    set<int> C; 
    C.insert(A); 
    set<int> pump = SetUnion(B , C); 
    return pump; 
} 
set<int> operator%(set<int> A , set<int> B) 
{ 
    return SymmetricDifference(A , B); 
} 
set<int> operator%(set<int> A , int B) 
{ 
    set<int> C; 
    C.insert(B); 
    set<int> pump = SymmetricDifference(A , C); 
    return pump; 
} 
set<int> operator%(int A , set<int> B) 
{ 
    set<int> C; 
    C.insert(A); 
    set<int> pump = SymmetricDifference(B , C); 
    return pump; 
} 
set<int> operator~(set<int> A) 
{ 
    set<int> pump; 
    vector<int> hose; 
    for(set<int>::iterator cycle = A.begin() ; cycle != A.end() ; ++cycle) 
    { 
     hose.push_back(*cycle); 
    } 
    int last_value = 
} 

ostream& operator<<(ostream& out , set<int>& B) // tus koj hlub 
{ 
    int count=0; 
    if(B.size() == 0) 
    { 
     out << "{}"; 
     return out; 
    } 
    else 
    { 
     set<int>::iterator it; 
     out << "{"; 
     for(it = B.begin() ; it != B.end() ; ++it) 
     { 
      ++count; 
      if(count == B.size()) 
      { 
       out << *it; 
      } 
      else 
      { 
       out << *it << ", "; 
      } 
     } 
     out << "}"; 
     return out; 
    } 
} 

istream& operator>>(istream& in , set<int>& B) // tus koj hlub 
{ 
    int user_input; 
    while(1) 
    { 
     in>>user_input; 
     if(user_input == -1) 
      break; 
     B.insert(user_input); 
    } 
    return in; 
} 

Кроме того, почему я получаю ошибку на моем «< <» символ оператора в функции здесь:

ostream& operator<<(ostream& out , set<set<int>>& B) 
{ 
    int count=0; 
    if(B.size() == 0) 
    { 
     out << "{}"; 
     return out; 
    } 
    else 
    { 
     set<set<int>>::iterator it; 
     out << "{"; 
     for(it = B.begin() ; it != B.end() ; ++it) 
     { 
      count++; 
      if(count == B.size()) 
      { 
       out << *it; 
      } 
      else 
      { 
       out << *it << ", "; 
      } 
     } 
     out << "}"; 
     return out; 
    } 
} 

---

Ответ дается г Shields производит следующее сообщение об ошибке. Я пытаюсь выяснить, почему это не работает:

Error: class "std::_Tree_const_iterator, std::allocator>>>> "has no member "insert"

---

ОТВЕТ ОТ АВТОРА:

set<set<int>> PowerSet(const set<int> A) 
{ 
    set<set<int>> ps; 

    if(A.size() == 0) 
    { 
     ps.insert(set<int>()); 

     return ps; 
    } 

    set<int>::iterator it = A.begin(); 

    int n = *it; 

    set<int> s1 = A; 

    s1.erase(n); 

    set<set<int>> ps1 = PowerSet(s1); 

    set<set<int>> ps2; 

    for(set<set<int>>::iterator it = ps1.begin() ; it != ps1.end() ; ++it) 
    { 
     set<int> ss = *it; 

     ss.insert(n); 

     ps2.insert (ss); 
    } 

    for(set<set<int>>::iterator it = ps1.begin() ; it != ps1.end() ; ++it) 
    { 
     ps.insert(*it); 
    } 

    for(set<set<int>>::iterator it = ps2.begin() ; it != ps2.end() ; ++it) 
    { 
     ps.insert(*it); 
    } 

    return ps; 
} 

Answer 1

Этот код C++ ниже ужасно неэффективна, но я думаю, что это должно дать вам представление о том, как это сделать рекурсивно. Правило рекурсии в основном это:

• P({}) = {{}}
  • набор мощности пустого множества является множество, содержащее пустое множество
• P({n} U S) = { {n} U T | T in P(S) } U P(S)
  • каждый набор в наборе мощности {n} U S либо содержит n, либо не содержит n - ровно по одному для каждого набора в наборе питания S

Имейте в виду, что множество мощности K имеет набор мощности мощности 2^K. Поэтому вы не хотите выполнять эту операцию на любых больших наборах!

---

set<set<int>> PowerSet(set<int> A) 
{ 
    set<set<int>> PA; 
    if (A.empty()) 
    { 
     //case: P({}) = {{}} 

     PA.insert(A); 
    } 
    else 
    { 
     //case: P({n} U S) = { {n} U T | T in P(S) } U P(S) 

     int n = *A.begin(); 
     A.erase(A.begin()); 

     //A is now "S" from the explanation above this code 

     auto PS = PowerSet(A); 
     for (auto T = PS.begin(); T != PS.end(); ++T) 
     { 
      //add each set T from P(S) 
      PA.insert(*T); 

      //add each set T from P(S) with n included as well 
      T->insert(n); 
      PA.insert(*T); 
     } 
    } 
    return PA; 
}