Note: 本文中的程序来自Martin Ordersky在www.coursea.org上所开设课程中的样例代码，文章主要目的是讲述我对此类问题解法及scala lazy evluation的理解。
问题描述
给你一个容量为9升的杯子和一个容量为4升的杯子，水不限使用，要求精确得到6升水。这就是“倒水问题”。我这里会讲述一个试用scala穷举法实现的一个例子。
建模
首先我们对这个问题进行建模。这个问题可以泛化为如下形式：
两个容量固定的杯子，可选的动作有：
初始状态为两个杯子都空，结束状态为其中一个杯子中的水量为所期望的结果。
从上面的描述中我们可以得到如下几个概念状态，动作，路径。
状态用于表述各个杯子中当前的水量，动作用来改变各个杯子中水量，路径用于表示到达某一状态的动作序列。
状态
我们可以用一个Vector[Int]来表述杯子的状态，下标为杯子编号，元素值为当前杯子中的水量，另外，我们还需要一个Vector[Int]表示杯子的容量，下标为杯子编号，元素值为杯子的容量。于是我们得到如下代码：
class Pouring(capacity: Vector[Int]) {
//States
val initialState = capacity map (x => 0)
}
capacity为杯子容量， intialState为问题初始状态。
动作
由上可知，解决这个问题可以有三种动作, Empty, Fill, Pour，每个动作都会导致状态发生变化，于是我们得到如下代码：
//Moves
trait Move {
def change(state: Vector[Int]): Vector[Int]
}
case class Empty(glass: Int) extends Move {
def change(state: Vector[Int]): Vector[Int] = state updated (glass, 0)
}
case class Fill(glass: Int) extends Move {
def change(state: Vector[Int]): Vector[Int] = state updated (glass, capacity(glass))
}
case class Pour(from: Int, to: Int) extends Move {
def change(state: Vector[Int]): Vector[Int] = {
val amount = state(from) min (capacity(to) - state(to))
state updated (from, state(from) - amount) updated (to, state(to) + amount)
}
}
注意因为要考虑杯子的容量和杯子中剩余的水量，Pour中的change方法稍微复杂了些。
路径
接下来到了最重要的路径部分了，路径是到达某一状态的动作序列，我们需要一个List[Move]表述动作序列，一个Vector[Int]表述结束状态。
还需要一个extend方法来扩展当前的动作序列，即在当前路径上，应用一个动作（Fill, Empty, Pour），得到一个新的路径。于是我们得到如下代码：
//Paths
class Path(history: List[Move], val endState: Vector[Int]) {
def extend(move: Move) = new Path(move :: history, move change endState)
override def toString = (history.reverse mkString " ") + " -->" + endState
}
算法
这里我们要采用的是穷举法：
穷举从初始状态出发所有可能的动作，以及可能达到的状态，再穷举从这些状态出发所有可能的动作以及可能达到的状态，如此反复，直到找到一个可能达到的状态满足期望，则到达这个状态所经历的所有动作组成的路径即为问题的解。
首先我们来穷举给定一组杯子可能的动作：
val glasses = 0 until capacity.length
val moves =
(for (g <- glasses) yield Empty(g)) ++
(for (g <- glasses) yield Fill(g)) ++
(for (from <- glasses; to <- glasses if from != to) yield Pour(from, to))
其次，在不进行任何动作时，动作列表为空，所达到的状态为初始状态，则：
val initialPath = new Path(List(), initialState)
接下来到最关键的部分了，穷举从初始状态出发的所有可能扩展出来的路径及其所达到的状态，由于从任何状态开始穷举，都会得到一个一组路径，而不是一个，于是我们首先定义一个从给定一组路径，穷举其可能扩展出来的的路径的方法：
def from(paths: Set[Path], explored: Set[Vector[Int]]): Stream[Set[Path]] = {
if (paths.isEmpty) {
Stream.empty
} else {
val more = for {
path <- paths
next <- moves map path.extend
if !(explored contains next.endState)
} yield next
paths #:: from(more, explored ++ (more.map(_.endState)))
}
}
paths为此次穷举的初始路径集合, explored用于记录已经穷举过的状态，以避免找出多条达到相同状态的路径，此方法通过穷举初始路径集合，在各个路径上扩展所有的动作，去掉那些达到状态已经被穷举过的路径，得到一组新的路径。
那么，从初始路径出发，其可能扩展出来的路径极其可能达到的状态如下：
val pathSets = from(Set(initialPath), Set(initialState))
对于给定的目标水量，遍历上述穷举结果路径找出endState包含目标水量的路径，如下：
def solutions(target: Int): Stream[Path] = {
for {
pathSet <- pathSets
path <- pathSet
if path.endState contains target
} yield path
}
总结
我们知道，穷举是一个无穷无尽的过程，上面的程序是如何运行的呢？其实是scala中强大的lazy load发挥了作用。我们再来看from方法的返回值类型，是Stream[Set[Path]], Stream 用于表述元素序列，它的一个重要特点是，只有需要使用到其中的某个元素时，程序才会去计算这个元素。于是，在程序运行时，scala并不会一下子把所有可能的路径都计算出来。对于solutions方法，也是一样。因此，scala只有在从solutions的计算结果中获取满足条件的路径时，pathSet才会穷举可能的路径，并且在找到满足条件的路径后，计算会立即结束，不会再列举其余的可能。