Конечных множеств счётное число(?)

[Xaositect]

arseniiv в сообщении #372208 писал(а):

Как раз деревьями: запись TSet содержит односвязный список таких же записей; считается пустым множеством, если список пустой.

Хм
Я бы хранил в корне высоту дерева. Сравнивать сначала высоту дерева и длину списка поддеревьев - если больше, то дерево больше. А вот если они равны, то все равно придется в рекурсию уходить

[arseniiv]

Просто тут же надо изоморфность проверять, а это легко сделать, если поддеревья упорядочены. А если неупорядочены, придётся сравнивать каждое поддерево одного дерева со всеми поддеревьями другого… Высота и количество поддеревьев, конечно, помогут, но можно найти довольно много деревьев, имеющих равные высоту и кол-во поддеревьев, если они хотя бы несколько больше 1.

[Xaositect]

Ну можете хэш какой-нибудь хранить в корне и сравнивать по нему. А если хэши равны, то уже честно.
В принципе высота-ширина - это простейший такой хэш. Можно взять отображение $s$ с учетом того, что int ограничен, и высоту.

[arseniiv]

Я ещё думал о том, чтобы все изоморфные деревья, которые соответствуют одному и тому же множеству, хранить в одном экземпляре, и чуть что все ссылки делать на этот единственный экземпляр. Тогда проверка на равенство будет просто замечательная — равны ли указатели. Но вот этот метод не совсем я ещё понял, как реализовать (у меня там есть конструктор пустого множества и метод добавления элемента, потому только в нём одном и надо проверять, не получилось ли что-то, что уже есть). Стоит ли игра свеч?

[Xaositect]

По-моему, пора уже применить первое правило оптимизации и написать что-нибудь, но так, чтобы при желании можно было изменить.
Вы, кстати, на C пишете?

[arseniiv]

Да.

[Профессор Снэйп]

arseniiv в сообщении #371982 писал(а):

Я неправильно выразился. Конечных множеств, все элементы которых конечны и все элементы их элементов, и т. д. конечны тоже.

Это называется "наследственно конечные множества". Доказать, что их счётное число, безусловно, можно.

-- Вс ноя 14, 2010 11:54:49 --

Xaositect опередил с термином

Доказывать, наверное, лучше не через деревья, а индукцией по ординальному рангу, который для любого наследственно конечного множества является натуральным числом.

-- Вс ноя 14, 2010 12:00:53 --

То есть... Для любого ординала $\alpha$ определим $R_\alpha$ индукцией по индексу:

$R_0 = \varnothing$
$R_{\beta + 1} = R_\beta \cup \mathcal{P}(R_\beta)$
$R_\gamma = \bigcup_{\delta < \gamma} R_\delta$, $\gamma$ предельный.

Аксиому регулярности можно переформулировать следующим образом: для любого множества $S$ найдётся ординал $\alpha$, такой что $S \in R_\alpha$. Наследственно конечные множества --- это, в точности, множества из $R_\omega$.

-- Вс ноя 14, 2010 12:07:49 --

Кодирование наследственно конечных множеств натуральными числами можно найти здесь.

[arseniiv]

Xaositect в сообщении #372216 писал(а):

А вот если они равны, то все равно придется в рекурсию уходить

Вот я как уточнил ваш способ для реализации. Он работает для номрализованных деревьев (см. ниже). Сначала сравниваем длину списка поддеревьев, потом сравниваем высоты. Если это не помогло, сравниваем списки поддеревьев как строки, как раз рекурсия тут. Нормализованные деревья — такие, у которых все поддеревья нормализованы и расположены в порядке возрастания по указанному выше отношению (т. е. ещё и без дубликатов). Конечно, дерево для пустого множества нормализовано.
Теперь надо будет придумать алгоритм нормализации поэффективнее.

[arseniiv]

(Забыл сказать, что тоже естественно, что множества будут храниться в таком нормализованном виде. Операции будут сохранять нормализацию, а при вводе она будет принудительная.)

[arseniiv]

arseniiv в сообщении #374976 писал(а):

Теперь надо будет придумать алгоритм нормализации поэффективнее.

Имею ввиду, что надо как-то эффективно засунуть удаление одинаковых поддеревьев в их сортировку. При том т. к. поддеревья хранятся указателями в односвязном списке, логично при сортировке создавать другой список, в конце заменяя им старый.

Придумал, как можно без хлопот удалять дубликаты: надо проверять, есть ли они в новом списке. Просто удаление дубликатов «переливанием» займёт $O(n^2)$. А вот сортировку не могу вспомнить никакую. Ага, нашёл сортировку слиянием с $O(n \log n)$. Только не придумаю, можно ли в неё как-то засунуть удаление дубликатов, но, наверно, нет. Тогда общая сложность нормализации будет $O(n^2)$ (без учёта сравнения поддеревьев), что вроде не страшно.

[Xaositect]

Ну, сортировку слиянием с удалением дублирующихся элементов можно сделать за $O(n\log n)$, это достаточно просто: при слиянии надо сравнивать не только головы сливаемых списков, но и последний на текщий момент элемент результата.

[arseniiv]

Кстати, что-то я вчера не подумал. Если просто проходить список поддеревьев после сортировки, можно за $O(n)$ удалить дубликаты. И сортировку "загрязнять" не надо.

[arseniiv]

Вообще не нужна специальная процедура нормализации с сортировкой и удалением дубликатов, ведь всё можно устроить так, чтобы список поддеревьев был всегда нормализованным! Только вчера додумался, ни странно.