在物理开关上枚举 2^n 如何使步骤最少

最后更新日期：2014-07-27

　　其实是玩一个游戏的时候想枚举…

　　问题是这样的：给你 n 个开关，每个开关可以处于 0 和 1 两种状态。现在需要遍历（在开关上拨出来）所有的 2ⁿ 种状态，求一种方案，使拨开关的次数最少。

　　设 n = 2 先看为什么 0 -> 1 -> 2 -> 3 这样按顺序来并不是最省的：

• 00 -> 01 拨 1 次
• 01 -> 10 拨 2 次（一个 0 -> 1 ，一个 1 -> 0）
• 10 -> 11 拨 1 次

　　共 4 次

　　但如果是 0 -> 1 -> 3 -> 2 的话：

• 00 -> 01 拨 1 次
• 01 -> 11 拨 1 次
• 11 -> 10 拨 1 次

　　共 3 次

　　好，下面我们用图论重新描述这个问题：

　　0 - 2ⁿ-1 每个数对应图上一个点。如果 a 和 b 这两个数的二进制表示中，只有一位不同，则称 a 和 b 的二进制距离为 1 ，连接 a 和 b 。于是这 2ⁿ 个点构成一个无向图。可以证明每个结点都恰跟其他 n 个结点相连。如果能找到这个图的一个哈密尔顿路，那么最少的拨开关次数就是 2ⁿ - 1 。

　　虽然通常需要先证存在性再找，不过下面这个 Scala 程序可以给出一种解答：

def leastTraverse(n: Int): List[Int] = {
  require(n >= 0)
  if (n == 0) {
    List(0)
  } else {
    val last = leastTraverse(n - 1)
    val d = 1 << (n - 1)
    last ++ last.reverse.map(_ | d) // 按位或
  }
}

　　n = 4 的结果：

0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8

　　至于原理是什么，我也不知道。我只是在观察自己凑出来的一组解时发现了一种镜像对称的规律。n = 3 时有这样一组解：

000
001
011
010
110
111
101
100

　　可以观察到 n 的部分相当于 n - 1 的部分倒过来并且在最高位都加上 1 。语言描述起来难度太高，具体的请看代码。

　　不过上面的代码要用到 List 和 reverse ，而我感觉可以不用把所有元素都保存下来，可以用 lazy evaluation。后来又想到一种相互递归（mutual recursion）的写法：

def leastTraverse0(n: Int): Stream[Int] = {
  require(n >= 0)
  if (n == 0) {
    Stream(0)
  } else {
    val d = 1 << (n - 1)
    leastTraverse0(n-1) ++ leastTraverse1(n-1).map(_ | d)
  }
}

def leastTraverse1(n: Int): Stream[Int] = {
  require(n >= 0)
  if (n == 0) {
    Stream(0)
  } else {
    val d = 1 << (n - 1)
    leastTraverse0(n-1).map(_ | d) ++ leastTraverse1(n-1)
  }
}

println(leastTraverse0(4).mkString(", "))
println(leastTraverse1(4).mkString(", "))

　　对称且颇能揭示原问题的本质。也许这就是代码的美吧。

　　那么如何证明上面的程序生成的就是原问题的一个解呢？先证 leastTraverse0(n) 和 leastTraverse1(n) 互为 reverse 关系，再用归纳法：假设 leastTraverse0(n-1) 和 leastTraverse1(n-1) 的所有数的二进制距离为 1 ，又由于 leastTraverse0(n-1) 的最后一个与 leastTraverse1(n-1) 的第一个相同（由 reverse 关系），而 map(_ | d) 改变了最高位，于是 leastTraverse0(n-1) 的最后一个和 leastTraverse1(n-1).map(_ | d) 的第一个的二进制距离为 1 ，证毕。