순서 집합과 자연 bijection (조합 종)

Question

A 일부 집합 (예 : 1000, 1001, 1002, ..., 1999)하자.

lessThan을 일부 순서 관계 함수 (예 : (a lessThan b) <-> (a > b))로 설정하십시오.

index에 A 요소를 Naturals에 매핑하는 함수 (역수인 index')로 설정하십시오.

예 :

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

가 index (및 index') 함수에 대한 모든 (또는 일부 종류) P (다항식 시간)에 (A, lessThan) 쌍을 만들 수있는 방법이 존재?

감사합니다. 미리 감사드립니다. 편집을 할

: A은 정의 (. 예를 들어, 또 다른 큰 부분 집합의 반복 모든 조합), 다음, 우리가 생각하지 수 A가 설정 한가 (P에서) 완전히에 이동입니다 수 있습니다.

편집을 할 : 다른 비 사소한 예를 들어, 우리는 각 삼중를 매핑 할 수 있습니다, 다음 An이

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

같은 요소가 구성 n X n 광장에 시계 방향으로 정렬 ((x, y, p) 같은 요소) 세트를하자 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); 
}; 

는 (I는 "조합 적 종", "Ordered construction of combinatorial objects", "species" haskell package을 다른 사람에 대해 읽고)

Answer 1

난 당신이 원하는 것을 오해 할 수 있지만, 경우에 아니에요 :

lessThan하면 정의를 세트에 전체 순서, 당신은

• 가 변환하여 index 및 index' 기능을 만들 수 있습니다 항
• lessThan하려면 NTC 요소의 유형을 감싸는 newtype은 생성자이다 index

Data.Map.fromDistinctAscList $ zip (map NTC sortedList) [1 .. ]로 구성 index'

Data.Map.fromDistinctAscList $ zip [1 .. ] sortedList로 구성하는 것이 정렬리스트 (또는 배열/벡터)

설정된 Ord 인스턴스가 lessThan에 의해 주어진 newtype의 집합입니다.

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는 정의에 의해 설정 될 수있다. (예를 들어, 또 다른 큰 부분 집합의 반복으로 모든 조합)를 선택한 다음, 우리는이 (P에서) 완전히에 이동입니다 가정 수 없습니다.

그런 경우, 내가 근본적으로 뭔가를 놓치지 않으면, index' 함수가 세트의 완전한 순회를 제공하기 때문에 원칙적으로 불가능합니다.

따라서 집합이 다항식 시간에서 순회 할 수있는 경우에만 index 및 index' 함수를 다항식 시간에 만들 수 있습니다.