2

假设我们有字典上的整数3,5,6,9,10,12 or 0011,0101,0110,1001,1010,1100，每个整数都设置了两个位。

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! /（纳米）！或 0 如果 m>n

例子：

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是两个设置位的位置，零是最不重要的位置，并且a总是大于b，那么您可以计算：

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

并且两个值之间的距离是两个值之间的差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 回答