algorithm - ハミングシリーズの生成

Question

私はプログラミングの問題を解決しようとしてきましたが、そのモジュールの1つでハミングシーケンスを生成する必要があります。この関数は、最初に2進数のNと10進数のKの2つの数値を入力します。これで、Nから最大Kのハミング距離を持つすべての可能な数値が生成されます。

この問題を解決する方法についてのアルゴリズムを私に提供していただければ、本当に助かります。

前もって感謝します。

Answer 1

アルゴリズムは非常に単純です。0からKまでのすべての可能な2進数を選択する必要があります。そして、次のように、Nでxorします。

    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

NextPermutation(1<<K)-1を開始して適用することにより、Kビットを設定してすべての数値を生成できます。 これらすべての数値をNでXORします。

Answer 3

非常に単純なアプローチ（パフォーマンスについては何も言及しなかったため）は、1からpまで反復し、数値のKビットが1に設定されている場合はNでビット単位の排他的論理和を行うことです。pのビット長はNと同じです。

擬似コード：

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

Answer 4

インタビューストリートではないですか？彼らはあなたに他の人にあなたのために問題をさせないように頼みます。