Определить лексикографическое расстояние между двумя целыми числами

Скажем, у нас есть целые числа лексикографий 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

Решение должно работать на любой вес, извините, я не был достаточно конкретным.

Имея номер
x = 2 k 1 + 2 k 2 + … + 2 k m
где k 1 2 <... m
можно утверждать, что положение числа x в лексикографически упорядоченной последовательности всех чисел с одинаковым весом для помех
lex_order (x) = C (k 1 , 1) + C (k 2 , 2) + … + C (k m , m)
где C (n, m) = n! / m! / (nm)! или 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

Если a и b являются позициями двух заданных бит, при этом нуль является наименее значимым положением и всегда больше 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 – вес взлома, а положение [i] – это положение бит i -го множества, считая от младшего значащего разряда, причем позиция наименее значимого установленного бита является position[1] .