8

一定の作業スペースで任意のサイズと任意のベース変換を行う方法はありますか? つまり、範囲内の一連の数値を、1 対 1 のマッピングを使用して範囲内の一連の数値に変換するには(必須でnはありませんが、望ましい) 辞書順を維持し、連続した結果を得るにはどうすればよいでしょうか?[1,m]ceiling(n*log(m)/log(p))[1,p]

パイプ関数として実行可能なソリューションに特に興味があります.eiは、RAMに保存できるよりも大きなデータセットを処理できます。

入力のサイズに比例する「作業スペース」を必要とする多くのソリューションを見つけましたが、一定の「作業スペース」を回避できるソリューションはまだありません。

シーケンシャル制約を削除しても違いはありますか? つまり、辞書順の連続した入力が非辞書順の出力になることを許可します。

F(1,2,6,4,3,7,8) -> (5,6,3,2,1,3,5,2,4,3)
F(1,2,6,4,3,7,9) -> (5,6,3,2,1,3,5,2,4,5)

いくつかの考え:

これはうまくいくでしょうか？

streamBase n -> convert( n, lcm(n,p)) -> convert( lcm(n,p), p) -> streamBase p

(ここでlcmは最小公倍数)

4

3 に答える 3

6

一般的にはありえないと思います。mがべき乗である場合p(またはその逆)、またはそれらが共通の基数の両方のべき乗である場合は、log m( p) の各グループが独立しているため、それを行うことができます。ただし、一般的なケースでは、数値を変換しているとします。基数に相当する数はa1 a2 a3 ... anp

sum(ai * mi-1のためiに1..n)

i最初の桁を処理したら、 ith 番目の部分和が得られます。i+1' 番目の部分和を計算するには、 を追加する必要があります。一般に、この数値はほとんどの場所でゼロ以外の数字になるため、これまでに処理したすべての数字を変更する必要があります。言い換えれば、最終的な出力数字がどうなるかを知る前に、すべての入力数字を処理する必要があります。ai+1 * mi

mが共通の基数のべき乗である特殊なケース、または同等に log m( p) が有理数である場合、前部近くのmi基数にゼロ以外の数字がいくつかあるだけなので、ほとんどの数字を安全に出力できます。pここまで計算しました。

于 2009-05-19T19:42:10.093 に答える
2

辞書順でストリーム指向の方法で基数変換を行う方法があると思います。ただし、私が考え出したことは、実際にそれを行うには十分ではなく、いくつかの仮定があります。

  1. 位置番号の長さはすでにわかっています。
  2. 記載されている数値は整数です。math と -ive インデックスで何が起こるかは考慮していません。

長さpの一連の値aがあり、各値の範囲は [0, m -1] です。[0, n -1]の範囲の長さqの値bのシーケンスが必要です。次のように、 aから出力シーケンスbのk番目の桁を計算できます。

b k = floor[ sum(a i * m i for i in 0 to p-1) / n k ] mod n

その合計を 2 つの部分に再配置し、任意の点zで分割します

b k = floor[ ( sum(a i * m i for i in z to p-1) + sum(a i * m i for i in 0 to z-1) ) / n k ] mod n

[0,z-1] の間の a の値がまだわかっておらず、2 番目の合計項を計算できないとします。範囲を処理する必要があります。しかし、それでもb kに関する情報が得られます。

b kの最小値は次のとおりです。

b k >= floor[ sum(a i * m i for i in z to p-1) / n k ] mod n

b kの最大値は次のとおりです。

b k <= floor[ ( sum(a i * m i for i in z to p-1) + m z - 1 ) / n k ] mod n

次のようなプロセスを実行できるはずです。

  1. zをpに初期化します。a の各文字を受け取るたびにpからカウントダウンします。
  2. bの最上位値のインデックスにkを初期化します。私の脳がまだ働いているなら、ceil[ log n (m p ) ].
  3. aの値を読み取ります。zを減分します。
  4. b kの最小値と最大値を計算します。
  5. 最小値と最大値が同じ場合、b kを出力し、k を減らします。4. ( b kのいくつかの連続した値に対して十分な値がすでにある可能性があります)
  6. z !=0 の場合、より多くのa の値が期待されます。3へ。
  7. うまくいけば、この時点で完了です。

範囲の値を効率的に計算する方法はまだ考えていませんが、 a の入力文字から合計を計算する方が、 a のすべてを格納するよりもはるかに合理的に実行できると確信しています。ただし、数学を行わずに、それについて難しい主張はしません!

于 2009-05-20T04:19:32.487 に答える