Головоломка: нужен пример «сложного» отношения / разбиения эквивалентности, которое запрещает сортировку и / или хеширование

Question

Из вопроса " Является ли разбиение легче, чем сортировка? ":

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

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

(Имейте в виду различие между равенством и эквивалентностью .)

Очевидно, что отношение эквивалентности должно учитываться при разработкеалгоритм упорядочения.Например, если отношение эквивалентности «люди, рожденные в одном и том же году, эквивалентны», сортировка по имени этого лица не подходит.

1. Можете ли вы предложить тип данных и отношение эквивалентноститакой, что невозможно создать порядок?

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

(Примечание: все в порядке, если неэквивалентные элементы отображаются нато же значение хеша (коллизия) - я не прошу решить проблему коллизий - но с другой стороны, hashFunc(item) { return 1; } обманывает.)

Я подозреваю, что для любой пары тип данных / эквивалентность гдеможно определить порядок, также можно определить подходящую хеш-функцию, и они будут иметь аналогичную алгоритмическую сложность.Контрпример к этой гипотезе был бы поучительным!

Answer 1

Ответ на вопросы 1 и 2 - «нет» в следующем смысле: если вычислимое отношение эквивалентности ≡ для строк {0, 1} ^*, существует вычислимая функция f такая, что x ≡ y тогда и только тогда, когда f (x) = f (y), что приводит к порядку / хэш-функции. Одно определение f (x) является простым и очень медленным для вычисления: перечислите {0, 1} ^* в лексикографическом порядке (ε, 0, 1, 00, 01, 10, 11, 000,… ) и вернуть первую строку, эквивалентную x. Мы гарантированно завершим работу, когда достигнем x, поэтому этот алгоритм всегда останавливается.

Answer 2

Создание хеш-функции и порядок могут быть дорогими, но обычно это возможно. Одна хитрость состоит в том, чтобы представить класс эквивалентности предварительно скомпонованным членом этого класса, например, членом, сериализованное представление которого является наименьшим, когда рассматривается как битовая строка. Когда кто-то вручает вам член класса эквивалентности, сопоставьте его с этим канонизированным членом этого класса, а затем хэшируйте или сравнивайте представление строки битов этого члена. Смотрите, например http://en.wikipedia.org/wiki/Canonical#Mathematics

Примеры, когда это невозможно или удобно, включают, когда кто-то дает вам указатель на объект, который реализует equals (), но ничего более полезного, и вы не можете сломать систему типов, чтобы заглянуть внутрь объекта, и когда вы получить результаты опроса, который только просит людей судить о равенстве между объектами. Кроме того, алгоритм Крускала использует внутреннее объединение и поиск для обработки отношений эквивалентности, поэтому, скорее всего, для этого конкретного приложения не найдено ничего более рентабельного.

Answer 3

Теоретически, это всегда возможно (для вопросов 1 и 2) из-за теоремы упорядочения скважин , даже если у вас есть несчетное количество разделов.

Даже если вы ограничиваете вычислимые функции, ответ throwawayaccount отвечает на это.

Вам нужно более точно определить свой вопрос: -)

В любом случае

Практически говоря,

Обратите внимание на следующее:

Ваш тип данных - это набор целочисленных массивов без знака. Порядок сравнения лексикографический.

Вы могли бы рассмотреть hash (x) = x, но я полагаю, что это тоже обман: -)

Я бы сказал (но больше не думал о получении хеш-функции, поэтому вполне может ошибаться), что разделение по порядку гораздо более практично, чем разделение по хешу, поскольку само хеширование может стать непрактичным. (Без сомнения, существует функция хеширования).

Answer 4

Как вы, вероятно, знаете, сортировка на основе сравнения занимает не менее O (n log n) времени (более формально вы бы сказали, что это Omega (n log n)).Если вы знаете, что существует меньше классов эквивалентности log2 (n), то разбиение происходит быстрее, поскольку вам нужно проверять эквивалентность только с одним членом каждого класса эквивалентности, чтобы определить, какой части в разделе вы должны назначить данный элемент.

Т.е. ваш алгоритм может выглядеть следующим образом:

For each x in our input set X:
    For each equivalence class Y seen so far:
        Choose any member y of Y.
        If x is equivalent to y:
            Add x to Y.
            Resume the outer loop with the next x in X.

    If we get to here then x is not in any of the equiv. classes seen so far.
    Create a new equivalence class with x as its sole member.

Если имеется m классов эквивалентности, внутренний цикл выполняется не более m раз, и в целом занимает время O (нм).Как отмечает ShreetvatsaR в комментарии, может быть не более n классов эквивалентности, так что это O (n ^ 2).Обратите внимание, что это работает, даже если на X нет общего порядка.

Answer 5

Один пример, который, кажется, соответствует вашему запросу, - это тип IEEE с плавающей запятой.В частности, NaN не сравнивается как эквивалент ни с чем другим (и даже не с самим собой), если вы не предпримете специальных шагов, чтобы определить, что это NaN, и всегда вызываете этот эквивалент.

Аналогично для хеширования.Если память служит, любое число с плавающей запятой со всеми битами значенияи, установленными в 0, обрабатывается как имеющее значение 0.0, независимо от того, что биты в показателе степени установлены.Я мог бы вспомнить, что это немного неправильно, но идея в любом случае одна и та же - правильный битовый шаблон в одной части числа означает, что он имеет значение 0.0, независимо от битовостальное.Если ваша хеш-функция не примет это во внимание, она будет выдавать разные хеш-значения для чисел, которые действительно сравниваются точно равными.

Answer 6

Предположим, что F (X) - это функция, которая отображает элемент некоторого типа данных T на другой такой же тип, такой, что для любого Y типа T существует ровно один X типа T, такой что F (X).) = Y.Предположим далее, что функция выбрана так, что, как правило, нет практического способа найти X в приведенном выше уравнении для заданного Y.

Определить F0 = X, F {1} (X) = F (X), F {2} (X) = F (F (X)) и т. Д., Поэтому F {n} (X) = F (F {n-1} (X)).

Теперь определимтип данных Q, содержащий положительное целое число K и объект X типа T. Определите отношение эквивалентности следующим образом:

Q (a, X) против Q (b, Y):

Еслиa> b, элементы равны, если F {ab} (Y) == X

Если a Если a = b, элементы равны тогда и только тогда, когда X == Y

Для любого заданного объекта Q (a, X) существует ровно один Z для F {a} (Z) == X.Два объекта эквивалентны, если бы у них был один и тот же Z. Один мог бы определить порядок или хэш-функцию на основе Z. С другой стороны, если F выбран так, что его обратное не может быть практически вычислено, единственный практический способ сравнения элементов можетиспользовать функцию эквивалентности выше.Я не знаю способа определения порядка или хэш-функции без знания максимально возможного значения «a», которое может иметь элемент, или наличия средства для инвертирования функции F.

Answer 7

I полагаю , что ...

1- Можете ли вы предложить тип данных и отношение эквивалентности так, чтобы не было возможности создать заказ?*

... это возможно только для бесконечных (возможно, только для неисчисляемых) множеств.

2- Как насчет отношения типа данных и эквивалентности, где возможно создать такое упорядочение,но невозможно определить хеш-функцию для типа данных, которая будет сопоставлять эквивалентные элементы с тем же хеш-значением.

... то же, что и выше.

Answer 8

РЕДАКТИРОВАТЬ: Этот ответ является неправильным

Я не собираюсь удалять его только потому, что некоторые комментарии ниже являются просветляющими

Не все отношения эквивалентностиподразумевает порядок

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

Если мы получим набор функций f (x): R -> R в качестве нашего типа данных и определим отношение эквивалентности как:

f is equivalent to g if  f(g(x)) = g(f(x)  [commuting Operators][1]

Тогда вы не сможете отсортировать по этомупорядок (не существует никакой инъективной функции с действительными числами).Вы просто не можете найти функцию, которая отображает ваш тип данных на числа из-за мощности пространства функции.