0

いくつかのセットをしましょうA（例1000, 1001, 1002, ..., 1999）。

lessThanいくつかの順序関係関数をしましょう（例(a lessThan b) <-> (a > b)）。

要素を自然にマッピングする関数（逆関数を使用）をindex作成します。index'A

例：

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

P（多項式時間）のすべての（またはある種の）ペアの関数を構築index（および）する方法がありますか？index'(A, lessThan)

よろしくお願いいたします。

編集済み：A定義によって設定される可能性があります（たとえば、別の大きなサブセットの繰り返しを伴うすべての組み合わせ）。その場合、A完全にトラバース可能であるとは想定できません（Pで）。

編集済み：もう1つの重要な例として、要素が時計回りに正方形に並べられ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]with O(1)（多項式）にマップできます。

与えられた1つのAn要素で。与えられた1つの要素で。indexBnO(1)Bnindex'AnO(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次のように作成できます。indexindex'

  • セットをリスト（または配列/ベクトル）に変換する
  • に従って並べ替えるlessThan
  • index'として構築Data.Map.fromDistinctAscList $ zip [1 .. ] sortedList
  • indexとして構築Data.Map.fromDistinctAscList $ zip (map NTC sortedList) [1 .. ]

ここで、は、インスタンスがで指定されるNTCnewtypeでセットの要素の型をラップするnewtypeコンストラクターです。OrdlessThan

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 に答える