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