algorithm - 有序集和自然双射(组合物种)

Question

让A一些集合(例如 1000, 1001, 1002, ..., 1999 )。

让lessThan一些顺序关系函数(例如 (a lessThan b) <-> (a > b) )。

让index一个函数(带反 index' )映射 A元素到自然。

例子:

index a = 2000 - a
index' n = 2000 - n

存在某种构造index的方法(和 index' )所有(或某些种类)的函数 (A, lessThan) P(多项式时间)中的对？

提前致以最诚挚的问候和感谢!

已编辑:A可以是定义的集合(例如，所有组合与另一个大子集的重复)，那么，我们不能假设 A是完全可遍历的(在 P 中)。

EDITED:另一个重要的例子，让An一个集合(包含类似 (x, y, p) 的元素)，其元素按顺时针顺序排列到 n X n 中正方形，像这样

 1    2    3    4
12   13   14    5
11   16   15    6
10    9    8    7

然后，我们可以映射 An 中的每个三元组至 Bn = [1..n^2]与 O(1) (多项式)。

给定一个 An我们可以的元素index至 Bn与 O(1) .给定一个 Bn我们可以的元素index'至 An与 O(1) .

// Square perimeter; square x = 1, 2, 3, ...
Func<int, int, int> perimeter = ( x, n ) => 4 * ( n - 2 * x + 1 ); 

// Given main diagonal coordinates (1, 1), (2, 2), ... return cell number
Func<int, int, int> diagonalPos = ( x, n ) => -4 * x * x + ( 4 * n + 8 ) * x - 4 * n - 3; 

// Given a number, return their square
Func<int, int, int> inSquare = ( z, n ) => (int) Math.Floor(n * 0.5 - 0.5 * Math.Sqrt(n * n - z + 1.0) + 1.0); 

Func<int, int, Point> coords = ( z, n ) => { 
    var s = inSquare(z, n); 
    var l = perimeter(s, n) / 4; // length sub-square edge -1 
    var l2 = l + l; 
    var l3 = l2 + l; 
    var d = diagonalPos(s, n); 
    if( z <= d + l ) 
        return new Point(s + z - d, s); 
    if( z <= d + l2 ) 
        return new Point(s + l, s + z - d - l); 
    if( z <= d + l3 ) 
        return new Point(s + d + l3 - z, s + l); 
    return new Point(s, s + d + l2 + l2 - z); 
}; 

(我读过“组合物种”，"Ordered construction of combinatorial objects"，"species" haskell package 等)

Answer 1

我可能误解了你的意思，但以防万一:

如果 lessThan 定义了集合上的全序，则可以通过以下方式创建 index 和 index' 函数

• 将集合转换为列表(或数组/向量)
• 根据 lessThan 排序
• 将 index' 构造为 Data.Map.fromDistinctAscList $ zip [1 .. ] sortedList
• 将 index 构造为 Data.Map.fromDistinctAscList $ zip (map NTC sortedList) [1 .. ]

其中 NTC 是一个新类型构造函数，将集合元素的类型包装在一个新类型中，其 Ord 实例由 lessThan 给出。

newtype Wrapped = NTC typeOfElements

instance Eq Wrapped where
    (NTC x) /= (NTC y) = x `lessThan` y || y `lessThan` x
-- that can usually be done more efficiently

instance Ord Wrapped where
    (NTC x) <= (NTC y) = not $ y `lessThan` x

EDITED: A could be a set by definition (eg. all combinations with repetition of another big subset), then, we can't suppose A is completely traversable (in P).

在那种情况下，除非我遗漏了一些基本的东西，否则原则上是不可能的，因为 index' 函数将提供对集合的完整遍历。

因此您可以在多项式时间内创建 index 和 index' 函数当且仅当集合在多项式时间内可遍历。