Сформулируем требование следующим образом: найти такой оператор F, что для любого набора (u, v, ...) будет выполнено:
F(u, v, ...)= F(v, u, ...)=F(всевозможные перестановки) (условие коммутативности), причем не существует любого другого элемента z != u, такого что выполняется:
F(u, v, ...)=F(z, v, ...)=F(всевозможные перестановки) (условие уникальности)*.
Или более привычно: u, v, ... являются простыми ключами, а F(u, v, ...) составным ключом в единственном числе.
Где это может пригодиться? При работе со словарями (Dictionary). Например, Вам необходимо поместить объект Obj в Dictionary, для этого нужно построить ключ key, но как же быть, если Obj идентифицируется множеством (u, v, ...), а как известно, элементы множества не упорядочены и мы не можем просто построить цепочку идентификаторов (key1, key2, ...) (по аналогии со вложенными Dictionary). Ключ в данной задаче находится как применение оператора F на искомое множество: key=F(u, v, ...).
Без ограничения общности можно принять, что набор есть множество строк и ограничиться набором из 2-х элементов.
Как оказалось, решение очень простое, для того чтобы построить уникальный ключ для множества из двух строк u и v, нужно посимвольно сравнить u и v, выбрав max = max(u, v), min = min(u, v) (в данном случае необходимо найти только либо max либо min), а далее выполнить простую конкатенацию (concat) полученых значений через разделитель (delimiter):
F(u, v) = max(u, v) + delimiter + min(u, v).
По аналогии задачу можно продолжить на n-мерный случай.
UPD*: Стоит заметить, что если вместо Dictionary использовать Hashtable, то условие уникальности ключа не обязательно (см. комментарии).
Всем спасибо!
И Всех с наступающим Новым Годом!
Если у кого есть более лучшее решение, то ждем его в комментариях.
ОтветитьУдалитьПомимо упорядочивания множества, можно строить хэш и по-другому.
ОтветитьУдалитьПусть элементы принадлежат домену D. Для простоты, можно считать, что D - это либо целые числа, либо строки или последовательности байтов (так как всегда от элементов можно взять хэш).
Пусть K(x,y) - какая-то коммутативная ассоциативная операция D x D -> D.
Тогда можно построить хэш-функцию вида H(K(x1, K(x2, K(x3, ... K(x(n-1), xn)...)), где H - какая-то функция.
За счет того, что K является коммутативной и ассоциативной, это значение не будет зависеть от порядка.
Вопрос только в том, чтобы придумать хорошую функцию K. Например, можно попробовать в качестве K взять функцию вида J(x,y) + J(y,x), где J - какая-нибудь функция - эта функция заведомо коммутативна.
К сожалению, насчет качества такого хэша я сказать ничего не могу.
xor?
ОтветитьУдалить@dmitry-vk
ОтветитьУдалитьВы все правильно сказали, но единственная проблема в построении функции K=K(x,y)
Например ф-ция J(x,y) + J(y,x) в пространстве строк не коммутативна, т.к. оператор "+" (concat) не коммутативен.
@Aikin
XOR не уникален для каждого набора.
Пример:
XOR(00,11)=11
XOR(10,01)=11
для 2-х разных наборов, одинаковые значения.
>Например ф-ция J(x,y) + J(y,x) в пространстве строк не коммутативна
ОтветитьУдалитьЯ имел в виду, что функция J применяется к числам. К строкам, например, можно применять последовательный XOR.
>XOR не уникален для каждого набора.
Разве речь идет не о хэш-функции?
Я наложил дополнительное условие уникальности на ключ, чтобы можно было работать, со словарем (подвидом хэш таблицы) без всяких коллизий по ключам.
ОтветитьУдалитьПри использовании обычной хеш таблицы, оператор XOR вполне подойдет, но тогда все-равно придется как-то разрешать хэш коллизии.
Спасибо за замечание, сейчас внесу обновление.