Задача на бинарное отношение

[Werwolf]

Хочу сказать сразу, помогать или решать задачу мне не надо, я её уже решил. Просто предложите какие-либо версии по решению. А условие, собственно, такое: задано множество, а на нем бинарное отношение путем указания пар элементов, что принадлежат бинарному отношению. Задание: определить свойства бинарного отношения (рефлексивность, симметричность, и т.д.), а также в случае эквивалентности определить разбитие на классы.

[незваный гость]

Если памяти и времени не жалко, построим отношение в матричной форме. Несмотря на расточительность, работает неплохо на практике даже для относительно больших матриц (такие задачи встречаются при построении компиляторов).

[Werwolf]

Вообще-то по условию нам памяти на матрицу не хватает (ну чтобы жизнь простой не казалась). Поэтому сначала предлагалось хранить список пар элементов. Я рассудил, что проверять свойства будет долго и нудно, поэтому данные храню в таком виде. Есть список элементов множества, из каждого выходит список ссылок на элементы множества. Ну а потом проверка на свойства тривиальна, кроме сравнимости. Интересно, можно ли еще как-то хитрее извратиться.

[PAV]

Можно попробовать сразу строить разбиение на классы эквивалентности. Есть общий список элементов, у каждого есть флаг - вложен ли уже этот элемент в какой-либо класс или нет (а лучше - номер класса). Берем произвольный элемент и строим список тех, которые входят с ним в один класс. Для этого перечисляем все, которые с ним находятся в отношении. Далее перемещаемся к следующему, добавляем все эквивалентные ему (кроме тех, которые уже добавили). И так до тех пор, пока не дойдем до конца списка. Одновременно с добавлением проверяем, что элемент сравним со всеми предыдущими. Как только находим несоответствие - возвращаем ошибку.

Когда заканчиваем с очередным классом, находим первый неучтенный элемент и строим новые классы начиная с него.

[незваный гость]

Упорствуя в своих заблуждениях, я предложу метаидею. По прежнему делать матрицу, но для нее посмотреть технику разряженных матриц. Таковых много, книжки умные писаны. А если матрица не разряженная, то работая со списками больше памяти проиграешь (на накладные расходы), чем выиграешь.