algorithm - 谜题:需要一个 "complicated"等价关系/分区的例子，它不允许排序和/或散列

Question

来自问题“Is partitioning easier than sorting?”:

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.

(请记住相等和 equivalence 之间的区别。)

显然在设计排序算法时必须考虑等价关系。比如等价关系是“同年出生的人是等价的”，那么按人名排序就不合适了。

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 时终止，因此该算法总是会停止。