Determin两个整数之间的字典距离 [英] Determin the lexicographic distance between two integers

问题描述

假设我们有lexicographicaly整数 3,5,6,9,10,12或0011,0101,0110,1001,1010,1100 每两个位设置

Say we have the lexicographicaly integers 3,5,6,9,10,12 or 0011,0101,0110,1001,1010,1100 Each with two bits set.

我要的是找到距离（有多少间辞书排列，而不做实际工作的排列）之间的发言权 3 和 5 用尽可能少的操作成为可能。

What I want is to find the distance(how many lexicographical permutations between them, without doing the actuall permutations) between say 3 and 5 using as few operations as possible.

的距离表如下

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;

So a function f(3,5) would return 1;

该功能将始终以相同的汉明权（组位相同数量）的参数。

The function will always take arguments of same Hamming weight (same amount of set bits).

没有阵列应该被使用。

任何想法将是巨大的。

修改

忘了提，任何设置位大小（汉明权重），我会一直使用第辞书置换（基础）作为第一个参数。

Forgot to mention, for any set bit size(the hamming weight) I will always use the first lexicographical permutation(base) as the first argument.

例如。

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

编辑2

该解决方案应该适用于任何汉明权重，对不起，我是不够具体。

The solution should work for any hamming weight, sorry I was not specific enough.

推荐答案

具有数
X = 2 ^{K <子> 1} +2 ^{K ₂} + ... + 2 ^{K <子>米}
其中k <子> 1 ＆LT; k ₂ ＆LT; ...＆LT; k <子> M
它可以被要求保护的数x的该位置中具有相同汉明的所有数字的字典顺序有序序列重量是
lex_order（X）= C（K <子> 1 ，1）+ C（K ₂ ，2）+ ... + C（K <子> M ，M）
其中，C（N，M）= N！/ M！/（N-M）！或者0，如果M> N

Having a number
x = 2^k₁+2^k₂+...+2^k_m
where k₁<k₂<...<k_m
it could be claimed that position of number x in lexicographically ordered sequence of all numbers with the same hamming weight is
lex_order(x) = C(k₁,1)+C(k₂,2)+...+C(k_m,m)
where C(n,m) = n!/m!/(n-m)! or 0 if m>n

例如：

3 = 2 ⁰ + 2 ¹
lex_order（3）= C（0,1）+ C（1,2）= 0 + 0 = 0

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

5 = 2 ⁰ + 2 ²
lex_order（5）= C（0,1）+ C（2,2）= 0 + 1 = 1

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

6 = 2 ¹ + 2 ²
lex_order（6）= C（1,1）+ C（2,2）= 1 + 1 = 2

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

9 = 2 ⁰ + 2 ³
lex_order（9）= C（0,1）+ C（3,2）= 0 + 3 = 3

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

这篇关于Determin两个整数之间的字典距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！