海明系列的代 [英] Generation of a Hamming Series

问题描述

我一直在试图解决规划问题，其中要求我产生海明序列的模块之一。所述函数接受输入两个数字第一二进制数N和另一十进制数K.现在应该产生具有高达选自N K A Hamming距离的所有可能的数字。

I have been trying to solve a programming problem, one of the modules of which requires me to generate Hamming sequences. The function takes input two numbers first a binary number N and another a decimal number K. It should now generate all possible numbers having a Hamming distance of up to K from N.

如果你给我提供了关于如何解决这一问题的算法，这将是非常有益的。

It would be really helpful if you provide me with an algorithm about how to solve this problem.

在此先感谢。

推荐答案

该算法是pretty的简单。你只需要选择所有可能的二进制数包含从0至K的。 ，然后用正异或，只是这样的：

The algorithm is pretty simple. You just need to chose all possible binary numbers contains from 0 to K ones. And then xor it with N, just like this:

    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值

Note: count of numbers that have Hamming distance up to K from N can be extremely big, as soon it exponentially grows depend on value of K.

这篇关于海明系列的代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！