有序集合和自然雙射（組合物種）

Question

讓A某些集合（例如1000, 1001, 1002, ..., 1999）。 （例如(a lessThan b) <-> (a > b)）。

讓index函數（與逆index'）映射A元素爲自然。

實施例：

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

存在着一些方法來構建index（和index'）函數的所有（或一些種）(A, lessThan)對在P（多項式時間）？

最好的問候，並提前感謝！

EDITED：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是NEWTYPE構造包裝元素的類型該集合的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可以是一組定義（如：與其他大集的重複所有組合），那麼，我們不能假設A是完全穿越（以P）。

在這種情況下，除非我錯過了基本的東西，否則原則上是不可能的，因爲index'函數將提供對該集合的完整遍歷。

因此，您可以在多項式時間內創建index和index'函數，當且僅當該集合在多項式時間內可遍歷。