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

从问题“Is partitioning easier than sorting?”:



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

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

您能否建议一种数据类型和等价关系，以便无法创建排序？

可以创建这样的排序的数据类型和等价关系如何，但不可能在数据类型上定义将等效项映射到相同哈希值的哈希函数。

(注意:如果不等价的项目映射到相同的哈希值(碰撞)是可以的——我不是要求解决碰撞问题——但另一方面，hashFunc(item) { return 1; } 是在作弊。)

我怀疑对于任何可以定义排序的数据类型/等价对，也可以定义合适的哈希函数，并且它们将具有相似的算法复杂性。这个猜想的反例会很有启发性!

最佳答案

问题 1 和 2 的答案是否定的，在以下意义上:给定字符串 {0, 1}* 上的可计算等价关系 ≡，存在可计算函数 f，使得 x ≡ y 当且仅当 f(x) = f(y)，这导致了一个订单/散列函数。 f(x) 的一个定义很简单，计算起来也很慢:按字典顺序(ε, 0, 1, 00, 01, 10, 11, 000, ...)枚举 {0, 1}* 并返回第一个字符串相当于 x。我们保证在到达 x 时终止，所以这个算法总是停止。