algorithm - 海明级数的产生

Question

我一直在尝试解决一个编程问题，其中一个模块要求我生成汉明序列。该函数首先输入两个数字，一个是二进制数 N，另一个是十进制数 K。它现在应该生成所有可能的数字，这些数字与 N 的汉明距离最大为 K。

如果你能提供一个关于如何解决这个问题的算法，那将非常有帮助。

提前致谢。

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);

注意:从 N 到 K 的汉明距离的数字的数量可能非常大，因为它会很快呈指数增长，这取决于 K 的值。