Загадка: нужен пример “сложного” отношения эквивалентности / разделение, которое запрещает сортировку и/или хеширование

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

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

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

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

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

Как вы, наверное, знаете, сортировка на основе сравнения занимает как минимум 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 (нм) времени. Как отмечает ШритватсаР в комментарии, может быть не более n классов эквивалентности, так что это O (n ^ 2). Обратите внимание, что это работает, даже если нет полного заказа на X.

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

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

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

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

Практически,

Учтите следующее:

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

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

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

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

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

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

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

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

EDIT: Этот ответ неправильный

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

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

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

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

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

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

Предположим, что 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) vs Q (b, Y):

If a > b, элементы равны тогда и только тогда, когда F {ab} (Y) == X

Если a

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

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