алгоритм — Несколько вопросов о проверке, является ли множество в C ++ алгебраической группой
Я начал создавать библиотеку для работы с абстрактной алгеброй. Прямо сейчас я пытаюсь создать функцию, которая проверяет, является ли набор группой. Это должно быть само за себя:
В математике группа — это набор элементов вместе с операцией, которая объединяет любые два ее элемента в третий элемент, удовлетворяющий четырем условиям, называемым аксиомами группы, а именно замыкание, ассоциативность, тождество и обратимость. Одним из наиболее знакомых примеров группы является набор целых чисел вместе с операцией сложения; сложение любых двух целых чисел образует другое целое число. (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)внутри моего гнезда петель? я - Позже я хотел бы проверить, являются ли целые наборы нативных объектов такими, как
intа такжеlongявляются группами. Как я могу установитьS1равныйstd::setиз всехlongs?
Решение
Вы должны создать класс, чтобы выразить понятие множества с помощью операции 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 (или же е) элемент (это 0 для целых чисел) р с (операция называется) добавление +, но 1 для целых R \ 0 с умножением «х»). Вам нужно добавить 1 в ваш класс. Абсолютно необходимо проверить (3) и (4). Далее личность 1 не целое число 0 в целом, но описание некоторых специальных элемент идентичности это даст тот же элемент х если сам х подлежит эксплуатации + с 1 ,(е), а также 1 + х = х. (Вы можете пропустить одно выражение, если операция «+» коммутативна, что верно, если 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), е за + задается парой [0,1] и дляИкс«на [1,1]. Поэтому, чтобы сделать это более общим, вы должны перебрать элементы, выберите е и позвонить 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;
}
Другие решения
Сначала ошибка: ассоциативность тоже требует оп, а не +.
Закрытие выглядит нормально.
Нейтральный элемент: ну, вы должны искать элемент N
так что каждый элемент A множества op(A,N)=A а также op(N,A)=A
(эти две вещи не совпадают)
Должно быть такое N, или это не группа.
Попробуйте каждый элемент для N, а в цикле N каждый A …
И обратные элементы: для каждого элемента A должен быть B (может быть таким же, как A)
чтобы op(A,B)=N (N ранее)
Эти вещи легко поместятся в ваши петли.
Every A {Every B {...}}
N известен.
НО: если вы хотите работать с большими наборами данных, такими как все длинные (или даже бесконечные вещи)
Вы больше не можете использовать такие простые методы (даже ассоциативность и т. д. плоха)
И спрашивать о переопределении Mathematica и т. Д. Немного больше …