0

让A一些设置（例如1000, 1001, 1002, ..., 1999）。

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

让index一个函数（带有 inverse ）将一个元素index'映射到自然值。A

例子：

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

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

最好的问候和提前感谢！

EDITED：A根据定义可能是一个集合（例如，所有组合与另一个大子集的重复），然后，我们不能假设A它是完全可遍历的（在 P 中）。

编辑：另一个不平凡的例子，让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); 
};

（我读过“组合物种”、“组合对象的有序构造”、“物种”haskell 包等）

4

1 回答 1

3

我可能会误解你想要什么，但万一我不是：

如果lessThan在集合上定义了一个总订单，您可以通过以下方式创建index和index'函数

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

其中NTC是一个 newtype 构造函数，它将集合元素的类型包装在一个 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

编辑： A 可以是定义的集合（例如，所有组合与另一个大子集的重复），然后，我们不能假设 A 是完全可遍历的（在 P 中）。

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

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

于 2012-12-20T13:26:42.050 回答