Поколение серии Хэмминга

Question

Я пытался решить проблему программирования, один из модулей которой требует от меня генерации последовательностей Хэмминга. Функция принимает входные два числа, сначала двоичное число N, а другое - десятичное число K. Теперь она должна сгенерировать все возможные числа, имеющие расстояние Хемминга до K от N.

Было бы очень полезно, если бы вы предоставили мне алгоритм решения этой проблемы.

Заранее спасибо.

Answer 1

Алгоритм довольно прост. Вам просто нужно выбрать все возможные двоичные числа, содержащие от 0 до K единиц. А затем скомпонуйте его с помощью N, вот так:

    public static Char[] Xor(Char[] a, Char[] b)
    {
        Char[] c = new Char[a.Length];
        for (Int32 i = 0; i < a.Length; ++i)
            if (a[i] == b[i])
                c[i] = '0';
            else
                c[i] = '1';

        return c;
    }

    public static void Generate(Char[] original, Char[] current, int position, int k)
    {
        if (position == original.Length)
        {
            Console.WriteLine(Xor(original, current));
            return;
        }

        if (k > 0)
        {
            current[position] = '1';
            Generate(original, current, position + 1, k - 1);
        }

        current[position] = '0';
        Generate(original, current, position + 1, k);
    }

    // Find all Number with hamming distance up to 2 from 01100
    Generate("01100".ToCharArray(), "00000".ToCharArray(), 0, 2);

Примечание: число чисел, которые имеют расстояние Хэмминга до K от N, может быть чрезвычайно большим, так как вскоре оно растет в геометрической прогрессии, зависит от значения K.

Answer 2

Вы можете сгенерировать все числа с K установленными битами, начиная с (1<<K)-1 и применяя NextPermutation до тех пор, пока не получите их все.
XOR все эти числа с N.

Answer 3

Разве это не для Интервью-стрит?Они просят вас не заставлять других делать для вас проблемы.

Answer 4

Очень простой подход (так как вы не упомянули что-то о производительности) состоит в том, чтобы выполнить итерацию от 1 до p и поразрядно записать ее с N, если число меньше K бит, установленное как 1. p имеет ту же длину в битах, что иN.

Псевдокод:

for i in [0..p]
   if countBits(i) <= K then
      result.add(p xor N)
   end
end