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

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

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

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

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

  共 4 次

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

  共 3 次

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

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