c++ - 幂集 ~ 递归 ~ Hasse 图

Question

(另见下文)

因此，我已经为正在编写的集合操作程序编写了一些函数和一些运算符，而且我也希望将幂集作为实用程序使用(不要介意代码中的注释)。我不想使用二进制方法，但我想使用递归。我在 Ralph Oberste-Vorth 的通往抽象数学的桥梁一书中看到了幂集的定义(第 65 页)，在下一页我看到了所有这些等价关系，例如“如果 S = X，则 P(S ) = P(X)”和“如果 A 和 B 是集合，则 P(A) U P(B) = P(A U B)”，我想起了递归。我认为递归可以在这里工作，但我不确定。我在玩 Mathematica 的 Combinatorica 包，那个 Haverford College paper在 Hasse Diagrams 上，我认为我可以解决问题，就像所做的一样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 | P(S) } U P(S) 中的 T
  • {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;
}