algorithm - 非递归格雷码算法理解

Question

这是算法书中的任务。

问题是我完全不知道从哪里开始!

Trace the following non-recursive algorithm to generate the binary reflexive
Gray code of order 4. Start with the n-bit string of all 0’s. 
For i = 1, 2, ... 2^n-1, generate the i-th bit string by flipping bit b in the 
previous bit string, where b is the position of the least significant 1 in the 
binary representation of i. 

所以我知道1位的格雷码应该是0 1，2位的格雷码应该是00 01 11 10等等。

很多问题

1) 我知道对于 n = 1 我可以从 0 1 开始吗？

2)“以全0的n位字符串开头”该如何理解？

3) “前一个位串”？哪个字符串是“前一个”？先前的意思是来自较低的 n 位？ (例如，对于 n=2，前一个是 n=1 中的那个)？

4) 如果唯一的操作就是翻转，我该如何将 1 位字符串转换为 2 位字符串？

这让我很困惑。到目前为止，我理解的唯一“人类”方法是:从较低的 n 位获取集合，复制它们，反转第二组，向第一组中的每个元素添加 0，向第二组中的每个元素添加 1。完成(示例:0 1 -> 0 1 | 0 1 -> 0 1 | 1 0 -> 00 01 | 11 10 -> 11 01 11 10 完成。

感谢您的帮助

Answer 1

您的所有四个问题的答案是，该算法不会以较低的 n 值开始。它生成的所有字符串都具有相同的长度，并且第 i 个(对于 i = 1, ..., 2ⁿ-1)字符串是从第(i-1)个生成的。

这是 n = 4 的前几个步骤:

以 G₀ 开头 = 0000

要生成 G₁，请翻转 G₀ 中的第 0 位，因为 0 是位置1 = 0001_b 二进制表示中最低有效 1 的值。 G₁ = 0001。

要生成 G₂，请翻转 G₁ 中的 1-st 位，因为 1 是位置2 = 0010_b 的二进制表示中最低有效 1 的值。 G₂ = 0011。

要生成 G₃，请翻转 G₂ 中的第 0 位，因为 0 是位置3 = 0011_b 的二进制表示中最低有效 1 的值。 G₃ = 0010。

要生成 G₄，请翻转 G₃ 中的 2-nd 位，因为 2 是位置4 = 0100_b 的二进制表示中最低有效 1 的值。 G₄ = 0110。

要生成 G₅，请翻转 G₄ 中的第 0 位，因为 0 是位置5 = 0101_b 的二进制表示中最低有效 1 的值。 G₅ = 0111。