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 的值。

Answer 2

(1<<K)-1您可以通过从 at 开始并应用NextPermutation来生成所有设置了 K 位的数字，直到您拥有所有数字。
将所有这些数字与 N 异或。

Answer 3

这不是专访街吗？他们要求您不要让其他人为您解决问题。

Answer 4

一个非常简单的方法（因为您没有提到有关性能的内容）是迭代 1 到 p 并与 N 进行按位异或，如果该数字设置为 1 的位数少于 K。p 的位长度与 N 相同。

伪代码：

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