问题标签 [gray-code]

最近有一个问题是：编写将十进制数转换为n位格雷码的算法。

例如：使用 1 位（最简单）：

使用 2 位

使用 3 位

I'm trying to implement an algorithm to get all combinations of k elements out of a set of n elements where the difference between two consecutive combinations are maximized (so kind of reverse Gray codes). In other words, the combinations should be ordered to avoid elements from appearing twice in a row, and so that no element is unnecessarily discriminated.

Ideally, the algorithm would also NOT pre-calculate all combinations and store them into memory, but rather deliver combinations on demand. I have searched extensively for this and found a few detailed answers such as https://stackoverflow.com/a/127856/1226020, but I can't seem to apply this. Also, many of the articles linked in that answer are paid content.

To illustrate what I mean:

From a set of [0, 1, 2, 3, 4], find all combinations of two elements. Using a simple algorithm that tries to increment the right-most element until no longer possible, then moving left, incrementing the previous digit etc, I get the following results:

I produce this result with the following Java code:

This is not what I want, because I want each consecutive combination to be as different as possible from the previous one. Currently, element "1" appears four times in a row, and then never again. For this particular example, one solution would be:

I have indeed managed to accomplish this result for this particular case by applying a sorting algoritm after the combinations are generated, but this does not fulfill my requirement of on-demand combination generation as the entire set of combinations has to be generated at once, then sorted and kept in memory. I'm not sure it works for arbitrary k and n values either. And finally, I'm pretty sure it's not the most efficient way as the sorting algorithm basically loops through the set of combinations trying to find one sharing no elements with the previous combination. I also considered keeping a table of "hit counts" for each element and use that to always get the next combination containing the lowest combined hit count. My somewhat empirical conclusion is that it will be possible to avoid elements from completely appearing in two consecutive combinations if n > 2k. Otherwise, it should at least be possible to avoid elements from appearing more than twice in a row etc.

You could compare this problem to what is achieved for k = 2 using a standard round-robin scheme for football games etc, but I need a solution for arbitrary values of k. We can imagine this to be a tournament of some sort of game where we have n players that are to play against all other players in a set of games, each game holding k players. Players should as far as possible not have to play two games in a row, but should also not have to wait unnecessarily long between two game appearances.

Any pointers on how to solve this either with a reliable sorting algorithm post generation, or - preferably - on-demand, would be awesome!

Note: Let's typically assume that n <= 50, k <= 5

Thanks

The problem is to tell if two 8-bit chars are gray codes(differ only in 1 bit) in C++? I found an elegant C++ solution:

I was confused that what does the "& 0xff" do?

我的任务是使用递归打印出格雷码。用户在 之间输入一个位值，因此您可以拥有0-8的最大数量是 256 (2^8)。strings

我已经完成了基本案例，但我不知道我会为 else 部分做什么。

到目前为止我的代码：

我正在寻找一种算法，它遍历 n 个元素集的所有 k 个元素子集。我不想显式地生成所有这些子集。

有一种简单的算法可以做到这一点，即按字典顺序对相应的位向量进行排序，然后从当前子集转到下一个子集。

尽管如此，我寻求一种在每一步中只切换 2 位的算法。我读过这样的代码称为“灰色代码”，但我没有找到解决我的问题的算法。

是否有一个直接的实现？

对于通信系统，我需要一种特殊的格雷码。要求是：

1. 像所有格雷码一样，两个连续的值只有一位不同。
2. 同一位上的两个转换应该至少远离一些任意数量的值。这个距离被记录为最小运行长度的mrl。
3. 我不关心从最后一个代码到第一个代码的距离，代码翻转时对 mrl 没有限制。

这种格雷码的一个例子是，对于 5 位和 mrl = 4：

本文给出了不同位数的最佳 mrl 值。但是，这些值是“通过使用详尽的计算机搜索”找到的

我有适用于少量位数（最多 6 位）的 python 代码：

我的问题是我想要一个 20 位的代码，而基本方法的复杂性似乎接近 O(n^3)。有关如何改进此代码的任何建议？有更好的方法吗？

我有这个函数，给定一个格雷码，返回下一个格雷码。您可以在此处找到有关其工作原理的更完整说明。问题是我想让这个增量函数模块化，以便递增对应的格雷码UINT_MAX返回对应的格雷码0（分别是最高有效位和0）。由于这不是默认行为，因此我为这种特殊情况添加了检查。这是完整的算法：

所以，实际的问题实际上是关于分支预测的。我经常读到__builtin_expect只有当一个分支真的很可能被选中或不太可能被选中时才使用它，常见的例子是在没有错误的情况下加速程序。

考虑到我没有处理错误情况，我不确定使用__builtin_expect这样的边界检查是否是一个好主意。这是一个使用的好地方__builtin_expect还是增加最大值是一个足够常见的操作来欺骗分支预测？

注意：与往常一样，评论和答案会突出显示我的问题中不清楚的事情:)

我将提供更多背景信息：此函数旨在成为库的一部分，为了成为库而开发，并且不被任何已知的实际项目使用。因此，添加__builtin_expect意味着我希望人们主要增加其他值而不是最大值；手头没有任何实际项目，我想知道这是否是一个安全的假设。

我试图了解格雷码的工作原理。如果我们给出任何非负整数 n（其中 n 是位数），那么我们需要打印它的格雷码序列。下面是一些例子

2 位格雷码序列

3 位格雷码序列

根据我的理解，格雷码序列从 0 开始，在一个格雷码中，两个连续的值只有一位不同。不知道2的格雷码是[0,1,3,2]怎么来的，3的格雷码是怎么来的[0,1,3,2,6,7,5,4]

我尝试构建一个结构光环境来进行 3D 扫描。

据我所知，如果我选择使用格雷码来重建 3D 模型，我必须实现以 2 次幂（2^x，x = 0 ~ 10）编码的特定模式。

也就是说，图案的分辨率必须至少为 1024 x 1024。

如果我的 DLP 投影仪仅支持高达 800 x 480 的分辨率怎么办？当格雷码图案分辨率变得太高时，它会投射莫尔图案（我试过）。我应该怎么办？

我的朋友建议我创建 1024 x 1024 的图案，并将它们“裁剪”成 800 x 480，

但我认为格雷码应该遵循特定的顺序和模式，我的朋友建议会创建几个不对称的图像。

有没有人和我一样的经历？

----------2015.8.4更新问题----------

我在想，如果我的投影仪不能完美投射高分辨率图案，我可以让它投射低分辨率的图案，例如从 2^0 到 2^6 吗？

还是格雷码严格要求从 2^0 到 2^10 的模式？否则格雷码不可用？

除了汉明距离，我什么都有。我不断收到错误“int() 无法使用显式基数转换非字符串”

这是我的代码：

输出应该看起来像

请帮忙！