c++ - C++中判断一个集合是否为代数群的几个问题

Question

我已经开始制作一个用于处理抽象代数的库。现在我正在尝试制作一个函数来检查一个集合是否是一个组。它应该是不言自明的:

在数学中，群是一组元素以及将其任意两个元素组合成第三个元素的运算，该第三个元素满足称为群公理的四个条件，即闭包、结合性、恒等性和可逆性。最熟悉的群例子之一是整数集和加法运算；任意两个整数相加形成另一个整数。 ( http://en.wikipedia.org/wiki/Group_(mathematics) )

#include <set>
#include <iostream>

template <typename ObType, typename BinaryFunction>
bool isGroup(const std::set<ObType> & S, BinaryFunction & op)
{
    /*
       isGroup returns true or false depending on whether the set S
       along with the operator op is a group in the Algebraic sense.
       That is, S is a group if and only if all the 4 following
       conditions are true: 
            (1) If a, b in S, then a op b in S
            (2) If a, b, c in S, then (a + b) + c = a + (b + c)
            (3) There is an element 0 in S such that a + 0 = 0 + a for all a in S
            (4) If a in S, then there is a b in S such that a + b = b + a = 0
    */
    typename std::set<ObType>::const_iterator beg(S.cbegin()), offend(S.cend());
    bool noProblems = true;
    for (std::set<ObType>::const_iterator ia = beg; ia != offend && noProblems; ++ia)
    {
        for (std::set<ObType>::const_iterator ia = beg; ib != offend && noProblems; ++ib)
        {
            // ---------- (1) --------------
            if (S.count(op(*ia, *ib)) == 0) 
                noProblems = false;
            // -----------------------------
            for (std::set<ObType>::const_iterator ic = beg; ic != offend && noProblems; ++ic)
            {
                // ---------- (2) -------------
                if (((*ia + *ib) + *ic) != (*ia + (*ib + *ic)))
                    noProblems = false;
                // ----------------------------
            }
        }
    }

    return noProblems;
}

template <typename T>
class Plus
{
    public:
        T operator() (const T & x, const T & y) { return x + y; };  
};

int main()
{
    std::set<int> S1 = { 0, 1, -1 };
    std::set<int> S2 = { 0 };
    class Plus<int> p;
    std::cout << isGroup(S1, p);
    return 0;

}

没有编译错误，但我有几个问题:

• 如何在我的循环嵌套中检查 (3) 和 (4)？我
• 稍后，我想检查整套 native 对象(如 int 和 long)是否是组。如何设置 S1 等于所有 long 的 std::set？

Answer 1

您应该创建一个类来表达集合的概念，其中包含操作 op (+)(注意:这个“+”是不是普通的算术+所以

// ---------- (2) -------------
if (((*ia + *ib) + *ic) != (*ia + (*ib + *ic)))
    noProblems = false;

是错误的，应该是这样的

// ---------- (2) -------------
if ( op( op(*ia,*ib), *ic) != op( *ia, op( *ib, *ic)))
    noProblems = false;

)，这个集合(一个容器)的值(或者更确切地说是元素)，以及一个叫做1(或e)元素的特殊元素(整数为 0 R 与(调用的操作)加法 +，但整数 R\0 与乘法“x”)为 1。你需要给你的类(class)加一个1。绝对有必要检查(3)和(4)。此外，identity 1 通常不是整数 0，而是对某些特殊identity element 的描述，如果 x 本身是受 + 与 1 ,(e), and 1 操作的制约>+ x = x。 (如果操作“+”是可交换的，则可以跳过一个表达式，如果 S 是交换群则为真)。

现在你将做什么取决于你是否愿意引入提示参数。要使用提示在给定集合中查找标识元素，您可以编写

template <typename ObType, typename BinaryFunction>
bool isGroup( const std::set<ObType> & S, BinaryFunction & op, ObType e)
{
 //... important define BinaryFunction as taking const args !
typename std::set<ObType>::const_iterator beg(S.cbegin()), offend(S.cend());
bool isGroup = true;
for (std::set<ObType>::const_iterator ia = beg; ia != offend && noProblems; ++ia)
{

        // ---------- (3) --------------
        if( op( *ia, e)) != *ia  || op( e, *ia)) != *ia) 
            isGroup = false;
        // -----------------------------

一般而言，这并不直接表示标识元素。我们众所周知的整数或其他算术类型的简单示例 + 只是最简单且不可扩展的一种，即在环 Z 的分数领域，Q(Z)，e + 由一对 [0,1] 给出，“x” 由 [1,1] 给出。因此，为了使其更通用，您必须遍历元素，选择 e 并调用 op 来检查 (3) 是否适用于所有元素。

template <typename ObType, typename BinaryFunction>
bool isGroup( const std::set<ObType> & S, BinaryFunction & op)
{
     //... important define BinaryFunction as taking const args !
    typename std::set<ObType>::const_iterator beg(S.cbegin()), offend(S.cend());

    for (std::set<ObType>::const_iterator ia = beg; ia != offend; ++ia)
    {

        // ---------- (3) -------------
        /* let e be an *ia */
        ObType e = *ia; 
        bool isGroup = true;
        for ( auto ia2 : S) {

            if( op( ia2, e)) != ia2  || op( e, ia2)) != ia2) {
                isGroup = false;
                break;
            }

            // identity found, set e_ in class to e and return
            if( isGroup) {
                e_ = e;
               return true;
            }
        }
    }

    /* identity not found, this is not a group */
    return false;
}