algorithm - 生成数字，具有高汉明距离

Question

我正在寻找一种快速生成 k 个小于 2^64 的非负整数的方法，其中，在基数为 2 的情况下，任意两个数字之间的最小汉明距离尽可能大。

例如，如果我正在寻找 k=4 个数字并且它们应该小于 2^4，它们可能是:
0000
0011
1100
1111
最小汉明距离为 2。

是否有一种快速算法可以为给定的 k 生成这些数字？我将以 10^4 的顺序得到 k。

或者，生成一组数字的算法也可以正常工作，这些数字成对地具有大于给定值的汉明距离。

Answer 1

这是一个相当简单的方法。找出最小的位数 = b 可以表示 k 个不同的数字。例如。对于 k=4 使用 b = 2 位。将 64 位分成大小为 2 的 block 。对于每个 block ，在可用的 2^b >= k 中为每个要生成的数字指定一个不同的数字。

例如对于 k=4 个数字，b 位是 00、01、10、11，这里有 4 种可能性:

0000

0101

1010

1111

如果你有 c 个 block ，那么每个数字在每个 c 个 block 中至少有一位与其他数字不同，所以最小保证汉明间隔是 c。

您还可以排列每个 block 中的数字选择，这会产生更多看起来随机的示例，例如

0011

0101

1000

1110