Существует ли какой-нибудь конструктивный (не переборный) алгоритм генерации
бинарных отношений на заданном множестве?
Набыдленный перебор(*) не удовлетворяет ни по скорости, ни по сжираемой памяти.
Вопросы:
- в какой структуре данных представлять бинарное отношение?
- можно ли сделать перебор проще?
- можно ли избавиться от перебора?
-----
(*)
Собственно, как выглядит переборный алгоритм какого-нибудь специфического
бинарного отношения (например, конгруэнций) над сетоидом (множеством с бинарной
операцией) A.
1) Генерируются всевозможные рефлективные симметричные бинарные отношения.
Рефлекивных симметричных бинарных отношений на множестве мощностью N всего
2^(N*(N-1)/2). Так как любой элемент данного множества либо связан либо не
связан заданным отношением с другим "большим" (допустим, что задан какой-то
порядок над множеством) элементом этого множества.
Таким образом, бинарное отношение [грубо говоря] представляется в виде
[((a,b),c)], где a и b ∈ A, c ∈ {true, false}.
Например, над A=[1,2,3] экземпляром рефлексивного симметричного бинарного
отношения будет [((1,2),true),((2,3),true),((1,3),false)].
2) Для каждого бинарного отношения, полученного по результатам прошлого шага,
проверяется транзитивность.
Для этого нужно взять каждые 2 пары из того листа, который представляет бинарное
отношение, и проверить, что если ((a,b),true) и ((b,c),true), то ((a,c),true).
Здесь сложность получается кубическая от длины листа бинарного отношения.
Например, вышеуказанный экземпляр эту проверку не проходит.
3) Для каждого бинарного отношения, полученного по результатам прошлого шага,
проверяется конгруэнтность.
Если ((a,b),true), то ((a*c,b*c),true) для любого c ∈ A.
Здесь сложность получается квадратичная от длины листа бинарного отношения.
-----
Для множеств размерностью 6-7 пизда уже полная
!
17 comments
recommend
bookmark
subscribe
В общем случае от перебора никак не избавиться. Если нужны только конгруэнции — перебор всех отношений эквивалентности выглядит попроще и поприятнее — разбивать множества на классы эквивалентности (хранить за O(n) для каждого элемента, в каком классе он сидит) и проверять конгруэнтность отношения (тут, увы, сходу не приходит в голову оптимизация).
> разбивать множества на классы эквивалентности
Интересно послушать алгоритм разбиения множества на классы эквивалентности.
> (хранить за O(n) для каждого элемента, в каком классе он сидит)
Что такое "хранить за O(N)"?
Из каких пределов перебирать для каждого элемента "номер" (или что там) его класса эквивалентности?
Храним массив, в котором для каждого элемента хранятся номера классов эквивалентности. Матрица не нужна.
Перебирать класс эквивалентности — от 0 до n, где n кол-во объектов. Пишется перебором с возвратом вида
def make_class_eq(object_number, class_number)
if (object_number == object_count)
yield class_eq;
foreach (i in range(0, class_number):
objects(object_number.set_class(class_number);
foreach(class_eq in make_class_eq(object_number + 1, class_numbers + (i == class_number)):
yield class_eq;
Откуда берётся object_count?
Примера использования ждать?
Лежит где-нибудь в области видимости. Количество объектов в исходном множестве, над которым строится отношение. Примера использования не ждать — код схематичен до отвращения. В принципе можно написать его более формально, если до конца понятно, о чём речь.
s/до конца/не до конца
Если не трудно, допиши до рабочего состояния.
Из-за размытости формулировок типа "Храним массив, в котором для каждого элемента хранятся номера классов эквивалентности." не совсем понятен вид финальной структуры, которая выплюнется из make_class_eq.
Судя по yield это питон, да?
Это попытка написать что-то питоноподобное, поскольку питона я не помню. Если нужен рабочий код — могу написать на плюсах (в этом случае в финальном состоянии будет вызываться некоторая функция) или на шарпе (там есть yield, плюс я его знаю чуть лучше, чем питон). Что предпочтительнее?
Впрочем ладно, пусть будут плюсы.
template < typename Function>
void UseFunctionToAllEqClasses(int curr_object_id, int objects_count, int curr_max_class_id, vector& < int > object_class, Function func) {
if (curr_object_id == objects_count) {
func(object_class);
} else {
for (int curr_obj_class = 0; curr_obj_class < curr_max_class_id) {
object_class[curr_object_id] = curr_obj_class;
UseFunctionToAllEqClasses(curr_object_id + 1, objects_count, curr_max_class_id, object_class, func);
}
object_class[curr_object_id] = curr_max_class_id;
UseFunctionToAllEqClasses(curr_object_id + 1, objects_count, curr_max_class_id + 1, object_class, func);
}
}
Вызывается это чудо дизайнерской мысли вот так:
vector < int > tmp.resize(objects_count);
UseFunctionToAllEqClasses(0, objects_count, 0, tmp, my_awesome_functor_which_will_store_all_needed_eq_classes_and_will_give_them_to_ me_whenever_i_ask);
Да, функтор должен понимать, что на входе у него только массив разбиения объектов на классы эквивалентности, и внутри него должен быть какой-нибудь объект сохранит его и будет возвращать object_class[obj1] == object_class[obj2], когда речь пойдёт о проверке наличия отношения.
А на чём-нибудь попроще, вроде хаскеля?
Хм. Пока что вижу простой способ исключительно в том, чтобы написать генератор следующего отношения по предыдущему. Но сейчас сходу не напишу. А перебор с возвратом как-то совсем некрасиво ложится.
ДА МНЕ ПОХУЙ
Можно извратиться и сразу полагаться на то, что у тебя отношение конгруэтно относительно сетоида. Если ты мне напомнишь, то я могу на haskell вечером написать.
Ну напиши.
https://gist.github.com/2414565