0

私は最近解決しようとしていた問題について多くの進歩を遂げてきましたが、特定の順序付けの問題についてアドバイスを得ることができます。私は、数字のリストの辞書式順序を表す方法を見つけようとしています。それぞれに独自の範囲があります(順序付けが懸念される前に定義されています)。

各リストには7 つの要素があります。各要素は、 0 から 0-3までの範囲を持つことができます。おそらく、具体的な例が役立つでしょう。

7 つの要素 [2、1、0、1、3、2、3] を持つ配列があります。このリストは、辞書編集順序を生成したい多数の可能なリストを抽象的に表しています。（編集：より明確にするために。各桁の値は、その桁が可能なリストのセットに含めることができる最大値を表します。そのため、例の最初の桁は基数 4 の数値と考えることができ、2 番目の桁は 4 進数と考えることができます。このリストの最初のいくつかの要素は次のようになります。

  1. [0, 0, 0, 0, 0, 0, 0]
  2. [1, 0, 0, 0, 0, 0, 0]
  3. [2, 0, 0, 0, 0, 0, 0]
  4. [0, 1, 0, 0, 0, 0, 0]
  5. [1, 1, 0, 0, 0, 0, 0]
  6. [2, 1, 0, 0, 0, 0, 0]
  7. [0, 0, 0, 1, 0, 0, 0]
  8. [1, 0, 0, 1, 0, 0, 0]

うまくいけば、パターンは明確です。次に、このシーケンスの m 番目の値を返す関数 f(m)を効率的に呼び出すことができるようにしたいと考えています。私が探しているものに非常に近いと思われるこの記事を見つけました (固定値の組み合わせを持つセットで辞書編集の m 位を取得する効率的な方法を提供します) が、間のギャップを埋めるのに問題があります2 つのアイデア (ただし、この記事で結果を再現しましたが、ある程度は理解できると思います)。

上記の例で提供されているものと同様の7つの要素リストによって定義されたシーケンスでm番目の値を返す関数 f(m) を作成する方法について誰かアイデアがありますか?

PS この問題が別の形で言い直されていて、見つけられなかった場合は申し訳ありません。私はかなりの調査を行いましたが、これに完全に対応するものは何もないようです. リンク、ブレインストーミング、一般的なアイデアはすべて大歓迎です!

編集 2: 最初の要素が 2 ではなく 3 だった私の例のエラーを修正しました。

4

1 に答える 1

1

編集：元の回答をはるかに簡単な変換に置き換えました。逆方向のソリューションを本当に見たい場合は、以前のリビジョンを確認してください。

指定した初期配列がサンプル リストと一致しないことに注意してください (配列の最初の要素は 2 である必要があります)。回答では、修正された配列を使用します。

入力配列 [2, 1, 0, 1, 3, 2, 3] が与えられた場合、各位置で可能な要素の数は、

[3,2,1,2,4,3,4]

3*2*1*2*4*3*4 = 576 の可能性が得られます。

リストの m番目のメンバーの値 (0 <= m < 576) を左端 (低位) の要素として決定するには、m/3 の余り、つまり m mod 3 を見つける必要があります。次の要素は (m div 3) mod 2 など。擬似コードでは、次のようになります。

increment all elements of A by 1

// we now have A = [3,2,1,2,4,3,4]
// m is given
// result is in R[7]
for i = 0 to 6
    R[i] = m mod A[i];
    m = m div A[i];
end

上記のサンプル リストを 0 から開始するように調整すると、同じ結果が得られるはずです。A = [3,2,1,2,4,3,4] および m = 11 を使用した計算例を次に示します。

11 mod 3 = 2 (11 div 3 = 3)
 3 mod 2 = 1 (3 div 2 = 1)
 1 mod 1 = 0 (1 div 1 = 1)
 1 mod 2 = 1 (1 div 2 = 0)
 0 mod 4 = 0
 0 mod 3 = 0
 0 mod 4 = 0

したがって、11 番目のリスト要素 (ゼロベース) は [2,1,0,1,0,0,0] です。

于 2012-11-16T22:00:46.203 に答える