1

（另见下文）

所以我有一些函数和一些运算符用于我正在编码的集合操作程序，我也希望将幂集作为一个实用程序（不要介意代码中的注释）。我不想使用二进制方法，但我想使用递归。我在 Ralph Oberste-Vorth 的书《通向抽象数学的桥梁》中看到了幂集的定义（第 65 页），在下一页我看到了所有这些等价性，例如“如果 S = X，则 P(S) = P(X)， ” 和“如果 A 和 B 是集合，那么 P(A) UP(B) = P(AUB)”，我想起了递归。我认为递归可以在这里工作，但我不确定。我在玩 Mathematica 的 Combinatorica 包，以及哈弗福德学院关于 Hasse Diagrams 的一篇论文，我想我可以解决，四分钟后，某种基于相应图表的某种方法，用于某组大小 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 先生给出的答案会产生以下错误。我试图弄清楚为什么它不起作用：

错误：类“std::_Tree_const_iterator，std::allocator>>>>”没有成员“插入”

作者的回答：

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;
}
4

1 回答 1

0

下面的 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;
}
于 2013-06-04T23:41:30.117 回答