2

3,5,6,9,10,12 or 0011,0101,0110,1001,1010,1100それぞれ 2 ビットが設定された辞書編集上の整数があるとします。

3私が望むのは、言うことと5できるだけ少ない操作を使用することの間の距離（実際の順列を行わずに、それらの間の辞書編集順列の数）を見つけることです。

距離表は以下の通り

3->5  = 1 or 0011->0101 = 0001
3->6  = 2 or 0011->0110 = 0010
3->9  = 3 or 0011->1001 = 0011
3->10 = 4 or 0011->1010 = 0100
3->12 = 5 or 0011->1100 = 0101

したがって、関数 f(3,5) は 1 を返します。

この関数は、常に同じハミング重み (同じ量のセット ビット) の引数を取ります。

配列は使用しないでください。

どんなアイデアでも素晴らしいでしょう。

編集

言及するのを忘れていましたが、設定されたビット サイズ (ハミングの重み)baseについて、最初の引数として常に最初の辞書編集順列 ( ) を使用します。

例えば

hamming weight 1 base = 1
hamming weight 2 base = 3
hamming weight 3 base = 7
...

編集 2

ソリューションは、ハミングの重みに対して機能するはずです。申し訳ありませんが、具体的ではありませんでした。

4

2 に答える 2

5

数
x = 2 k 1 +2 k 2 +...+2 k m
を持ち、 ここで k 1 <k 2 <...<k m
は、すべての数の辞書編集的に順序付けられたシーケンスにおける数 x の位置であると主張できます。同じハミング重みは
lex_order(x) = C(k 1 ,1)+C(k 2 ,2)+...+C(k m ,m)
で、C(n,m) = n!/m! です。 /(nm)! または m>n の場合は 0

例：

3 = 2 0 + 2 1
lex_order(3) = C(0,1)+C(1,2) = 0+0 = 0

5 = 2 0 + 2 2
lex_order(5) = C(0,1)+C(2,2) = 0+1 = 1

6 = 2 1 + 2 2
lex_order(6) = C(1,1)+C(2,2) = 1+1 = 2

9 = 2 0 + 2 3
lex_order(9) = C(0,1)+C(3,2) = 0+3 = 3

于 2012-11-25T21:07:18.480 に答える
3

aおよびbが2つのセットビットの位置であり、ゼロが最下位位置であり、a常により大きい場合、b次のように計算できます。

n = a*(a-1)/2 + b

2つの値の間の距離は、2つの値の差nです。

例：

3->12:
  3:  a1=1, b1=0, n1=0
  12: a2=3, b2=2, n2=5
  answer: n2-n1 = 5

これを他のハミング重みに拡張するには、次の式を使用できます。

n = sum{i=1..m}(factorial(position[i])/(factorial(i)*factorial(position[i]-i)))

ここmで、はハミング重みであり、position [i]はi最下位ビットから数えて'番目のセットビットの位置であり、最下位セットビットの位置はposition[1]です。

于 2012-11-25T20:00:28.843 に答える