难题：需要的一个例子的＆QUOT;复杂＆QUOT;等价关系/分区，不允许排序和/或散列 [英] Puzzle: Need an example of a "complicated" equivalence relation / partitioning that disallows sorting and/or hashing

问题描述

从这个问题：是分区比排序更容易？

假设我有一个项目和一个列表   等价关系在他们身上，   比较两个项目需要不断   时间。我要回的一个分区   的物品，例如的链接列表   列表，每个包含所有等同   项目。

Suppose I have a list of items and an equivalence relation on them, and comparing two items takes constant time. I want to return a partition of the items, e.g. a list of linked lists, each containing all equivalent items.

这样做的一种方法是延长   等同于对排序   项目并责令其（与排序   算法）;那么所有的等价物品   将毗邻。

One way of doing this is to extend the equivalence to an ordering on the items and order them (with a sorting algorithm); then all equivalent items will be adjacent.

（请记住平等和等价之间的区别。）

(Keep in mind the distinction between equality and equivalence.)

显然在设计排序算法时同值关系必须予以考虑。例如，如果同值关系是出生的人在同一年是等价，然后基于该人的名字排序是不恰当的。

Clearly the equivalence relation must be considered when designing the ordering algorithm. For example, if the equivalence relation is "people born in the same year are equivalent", then sorting based on the person's name is not appropriate.

1. 您能否提供一个数据类型和等价关系，使得它不可能创建一个排序？

1. Can you suggest a datatype and equivalence relation such that it is not possible to create an ordering?

怎么样的数据类型和等价关系它的是的可能创造这样的排序，但它的没有的可能对数据类型定义一个散列函数这将等效项映射到相同的散列值。

How about a datatype and equivalence relation where it is possible to create such an ordering, but it is not possible to define a hash function on the datatype that will map equivalent items to the same hash value.

（注：这是确定的，如果不等价的物品映射到相同的散列值（碰撞） - 我不要求解决冲突问题 - 但另一方面， hashFunc（项目）{返回1;} 是欺骗）

(Note: it is OK if nonequivalent items map to the same hash value (collide) -- I'm not asking to solve the collision problem -- but on the other hand, hashFunc(item) { return 1; } is cheating.)

我怀疑是对于任何数据类型/等效对其中可以定义一个顺序，它也将有可能定义一个合适的散列函数，它们将有类似的算法的复杂性。一个反例是猜想会有所启发！

My suspicion is that for any datatype/equivalence pair where it is possible to define an ordering, it will also be possible to define a suitable hash function, and they will have similar algorithmic complexity. A counterexample to that conjecture would be enlightening!

推荐答案

在回答问题1和问题2是否定的，在下面的意义：给出一个可计算的等价关系≡对字符串{0,1} ^* ，存在一个可计算函数f，使得且x≡y提示如果仅当f（x）= F（Y），从而导致订单/散列函数。 F（X）的一个简单定义是，而且速度很慢计算：枚举{0,1} ^* 字典顺序（ε，0，1，00，01，10，11，000， ...）并返回第一个字符串等价于x。我们保证，当我们到达X要终止，所以这种算法总是暂停。

The answer to questions 1 and 2 is no, in the following sense: given a computable equivalence relation ≡ on strings {0, 1}^*, there exists a computable function f such that x ≡ y if and only if f(x) = f(y), which leads to an order/hash function. One definition of f(x) is simple, and very slow to compute: enumerate {0, 1}^* in lexicographic order (ε, 0, 1, 00, 01, 10, 11, 000, …) and return the first string equivalent to x. We are guaranteed to terminate when we reach x, so this algorithm always halts.

这篇关于难题：需要的一个例子的＆QUOT;复杂＆QUOT;等价关系/分区，不允许排序和/或散列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！