1

一連のシーケンスを連続した整数にマップする方法について困惑しています。

すべてのシーケンスは次の規則に従います。

A_0 = 1
A_n >= 1
A_n <= max(A_0 .. A_n-1) + 1

そのようなシーケンスが与えられた場合、テーブルへのルックアップを行うための整数を計算し、テーブルへのインデックスを与えられた場合、シーケンスを生成できるソリューションを探しています。

例: 長さ 3 の場合、5 つの有効なシーケンスがあります。次のマップを実行するための高速関数 (できれば両方向) が良い解決策になります。

1,1,1   0
1,1,2   1
1,2,1   2
1,2,2   3
1,2,3   4
  • 演習のポイントは、有効なシーケンスとセルの間の 1 対 1 のマッピングでパックされたテーブルを取得することです。
  • セットのサイズは、可能な一意のシーケンスの数によってのみ制限されます。
  • シーケンスの長さがどのくらいになるかはわかりませんが、12 未満の小さい定数で、事前にわかっています。
  • 遅かれ早かれこれに着手しますが、それまでの間、コミュニティが「楽しむ」ためにそれを捨てます.

これらは異なる有効なシーケンスです

1,1,2,3,2,1,4
1,1,2,3,1,2,4
1,2,3,4,5,6,7
1,1,1,1,2,3,2

これらはそうではありません

1,2,2,4
2,
1,1,2,3,5

これに関連する

4

4 に答える 4

1

自然なシーケンスインデックスがありますが、計算はそれほど簡単ではありません。

A_0 = 1なので、n>0のA_nを探しましょう。

インデックス作成は2つのステップで行われます。

パート1：

A_n = max（A_0 .. A_n-1）+1の場所でシーケンスをグループ化します。これらの場所をステップと呼びます。

  • ステップには連続した番号（2、3、4、5、...）があります。
  • ステップ以外の場所では、1からインデックスがk未満のステップ数までの数値を入力できます。

各グループは、1がステップ、0が非ステップのバイナリ文字列として表すことができます。たとえば、001001010は、112aa3b4c、a <= 2、b <= 3、c<=4のグループを意味します。グループは2進数でインデックス付けされるため、グループの自然なインデックス付けがあります。0から2^length-1まで。グループバイナリ表現の値をグループ順序で呼び出します。

パート2：

グループ内のインデックスシーケンス。グループはステップ位置を定義するため、非ステップ位置の数値のみが可変であり、定義された範囲で可変です。これにより、さまざまな場所の辞書式順序を使用して、そのグループ内の特定のグループのシーケンスにインデックスを付けることが簡単になります。

1つのグループのシーケンス数を計算するのは簡単です。フォーム1^i_1 * 2 ^ i_2 * 3 ^ i_3*...の番号です。

組み合わせる：

これにより、2つの部分からなるキーが得られ<Steps, Group>ます。次に、これを整数にマップする必要があります。そのためには、ある値よりも小さい順序を持つグループ内のシーケンスの数を見つける必要があります。そのために、最初に、指定された長さのグループに含まれるシーケンスの数を見つけましょう。これは、すべてのグループを通過し、シーケンスの数などを繰り返して合計することで計算できます。T（l、n）を長さl（A_0は省略）のシーケンスの数とします。ここで、最初の要素の最大値はn+1になります。保持するより：

T(l,n) = n*T(l-1,n) + T(l-1,n+1)
T(1,n) = n

l + n <= sequence length + 1〜T（l、n）の値があるためsequence_length^2/2、簡単に計算できます。

次に、与えられた値以下の順序のグループでシーケンスの数を計算します。これは、T（l、n）値を合計することで実行できます。たとえば、順序が1001010バイナリ未満のグループ内のシーケンスの数は、次のようになります。

T(7,1) +         # for 1000000
2^2 * T(4,2) +   # for 001000
2^2 * 3 * T(2,3) # for 010

最適化：

これによりマッピングが得られますが、主要部分を組み合わせるための直接実装は>O(1)せいぜいです。一方、Stepsキーの部分は小さく、Groups各Steps値の範囲を計算することにより、ルックアップテーブルはこれをに減らすことができますO(1)。

上位の数式については100％確信が持てませんが、そのようなものになるはずです。

これらの発言と再発により、関数をシーケンス->インデックスおよびインデックス->シーケンスにすることができます。しかし、それほど些細なことではありません:-)

于 2010-12-07T14:39:17.463 に答える
1

ソートなしのハッシュが必要だと思います。

A0 は常に 0 から始まるので、数列を基数 12 の数字と考えて、その基数 10 を検索のキーとして使用できると思います。（これについてはまだわかりません）。

于 2008-12-15T19:53:16.800 に答える
0

これは、これらの値をファイルに保存し、関数に行を渡すことを前提として、Python関数です。

def valid_lines(lines):
    for line in lines:
        line = line.split(",")
        if line[0] == 1 and line[-1] and line[-1] <= max(line)+1:
            yield line

lines = (line for line in open('/tmp/numbers.txt'))
for valid_line in valid_lines(lines):
    print valid_line
于 2008-12-15T19:32:22.770 に答える
0

シーケンスが与えられたら、それをソートしてから、ソートされたシーケンスのハッシュをテーブルのインデックスとして使用します。

于 2008-12-15T19:36:57.707 に答える