algorithm - 使用 2^n 步来获得房间中每个可能的人组合

Question

这是消费税:

You start with an empty room and a group of n people waiting outside. At each step, you may either admit one person into the room, or let one out. Can you arrange a sequence of 2ⁿ steps, so that every possible combination of people is achieved exactly once?

---

我的解决方案是:

我可以有一个包含 n 个元素的位数组。每个元素的状态代表这个人是否在房间里。所以总共我们将有 2ⁿ 个不同的人组合在房间里。

算法可以是一个标准的回溯，列出所有的组合。

---

我在想是不是我的想法太天真了，还是太简单了？

这个消费税有什么陷阱吗？

---

编辑:

对于灰码的实现感兴趣的人，请看

http://yagni.com/graycode/

Answer 1

The algorithm can be a standard backtrack to list out all the combinations.

您的解决方案“有效”，但如果天真地实现，它将需要 2ⁿ 个步骤。

请参阅问题陈述中的以下句子:

At each step, you may either admit one person into the room, or let one out.

在您的解决方案中，当您列出所有位向量时，您可能会有 0111 后跟 1000，这意味着三个人将不得不离开房间，并且必须有一个人进入。

这需要 4 个步骤，而不是一个，因此您将获得远远超过 2ⁿ 个步骤来完成所有组合。

但是，您可以排列您描述的位向量，使得两个连续向量之间只有一位不同。这就是所谓的 Gray code .

这是来自维基百科文章的示例:

Dec  Gray   Binary
 0   000    000
 1   001    001
 2   011    010
 3   010    011
 4   110    100
 5   111    101
 6   101    110
 7   100    111

注意如何

1. 涵盖了所有位向量，并且
2. 对于每个连续的向量，只有一位发生变化。

这意味着您将能够以精确的 2ⁿ 步迭代所有组合。

如何实现这样的序列生成器在维基百科页面中也有解释，但如果这是一个练习，我建议你在偷看之前自己尝试一下;)