计算组合的数量是微不足道的。基本上，每两个字母之间都有一个字符。它可能是“epsilon”（空）或空格。因此，对于 n 个字母，您有 n-1 个这样的分隔符。由于每个字符只能有两个值，这与 n-1 位的二进制数相同。所以你可以有 2 的 n-1 次组合。
aids = 4 characters (n = 4)
n - 1 = 3
2 ** (n-1) = 8 combinations
现在，针对特殊情况。如果每个字符都可以是小写或大写，那就是字符的 n 次方（只要它们是字母）。现在，上面的每个组合都有 2 n 个基于大小写的变化，所以最终结果是 (2 (n-1)) * (2**n)，等于 2 ** (2*n -1)。
对于每个附加字母，您可以将枚举它们所需的时间加倍或加倍（取决于大小写），这可以从公式中轻松理解。
字符总数有点困难，但足以注意到每个“空格”有一半时间是“epsilon”。所以我们有 (2 ** (n-1)) * n (字母) + ((2 ** (n-1)) * (n-1)) / 2 (空格)。在示例中：
(2 ** 3) * 4 = 32 characters
(2 ** 3) * 3 / 2 = 12 spaces
Total = 44 characters
最后，距离问题与Levenshtein distance有关。我考虑过使用Burkhard-Keller 树，但我现在看到这根本没有必要，因为问题相当简单。
首先，使一个字符串等于另一个字符串所需的最小插入/删除/更改次数称为Levenshtein 距离。这直接适用于问题：您可以根据需要添加空格、删除空格、更改小写/大写。通常，最好使用动态编程来解决这个问题，这通常可以被认为是保存有关问题小部分解决方案的数据，然后在计算其他部分/更大部分时重用这些数据。
但是考虑到我们问题的特殊限制，我们可以只比较代表空格/epsilon 的“二进制”数字。
假设函数 f(word) 将返回表示该单词中空格的二进制数。例如，它将为“ai ds”返回“010”，为“aid s”返回“111”。每个组合之间的变化次数通过对 f (010 xor 111 = 101) 的结果进行异或运算得到，然后计算位数等于 1。让我们在 Scala 中为此编写几个函数：
def spacesToBinary(s: String) = {
(s zip s.drop(1)) // transform "ai ds" into ((a,i), (i, ), ( ,d), (d, s))
.foldLeft(0) { (binary, pair) => pair match {
case (' ', _) => binary // A space is always followed by a letter,
// so we ignore it
case (_, ' ') => (binary << 1) | 1 // If a letter is followed by a space, bit = 1
case _ => binary << 1 // If not, bit = 0
}}
}
def numberOfOnes(d: Int) = {
var bits = 0
var n = d
while(n != 0) {
if ((n & 1) == 1)
bits += 1
n >>= 1
}
bits
}
def spaceDistance(s1: String, s2: String) =
numberOfOnes(spacesToBinary(s1) ^ spacesToBinary(s2))
现在，一旦我们丢弃空格，比较小写/大写就很容易了：
def caseDistance(s1: String, s2: String) = {
val ns1 = s1 filter (_ != ' ')
val ns2 = s2 filter (_ != ' ')
(ns1 zip ns2).foldLeft(0){(acc, pair) => acc + (if (pair._1 == pair._2) 0 else 1)}
}
因此，Levenshtein 距离为：
def levenshtein(s1: String, s2: String) = spaceDistance(s1, s2) + caseDistance(s1, s2)
我们还知道关于 Levenshtein 距离的以下属性。假设 d(x,y) 是 x 和 y 之间的 Levenshtein 距离。然后我们知道：
d(x, y) = 0 if, and only if, x = y
d(x, y) = d(y, x)
d(x, y) + d(y, z) >= d(x, z)
最后一个标准我称为三角不等式。简单地说，从 x 到 z 的路径至少与从 x 到 y 的路径加上从 y 到 z 的路径一样小（想象一个具有顶点 x、y 和 z 的三角形）。
好的，让我们考虑一下奖金问题。
两个词之间有多少条路径？好吧，如果 Levenshtein 距离是 n，这意味着你有“n”个独特的修改，a1，a2，...，an。对于这些修改的每个不同顺序，您都有一个路径。“n”个元素的排列数是“n”（或n！）的阶乘：
def factorial(n: Int): Int = n match {
case 0 => 1
case _ => n * factorial(n-1)
}
2! = 2
3! = 6
4! = 24
5! = 120
etc
有没有“中心”组合？实际上，没有。如果我们回过头来将组合视为表示空格/无空格和小写/大写的二进制数对，那么很明显，您可以简单地反转位以产生一个新组合，其与所选组合的距离是最大可能。
或者，换句话说，对于 n 个字母的每个组合，只有一个对应的组合，因此两个组合之间的 Levenshtein 距离是 2*n - 1，即任意两个组合之间的最大可能距离。
我看到我忘记计算到 s 的（最小）距离为 n 的所有组合。好吧，我们知道每个组合都可以表示为两个二进制数，分别表示空格和每个字母的大小写，第一个是 n-1 位长，第二个是 n 位长。
我们还知道，我们可以简单地反转这些“数字”中的任何一个来获得差异。因此，如果我们得到一个 2*n - 1 位长的大二进制数，并且我们枚举它的所有位，则与它的最小距离 d 的组合由大小组中 2*n-1 位的组合给出“d”没有重复。对于 N=2*n-1，这种组合的数量是 N!/((Nd)!*d!)。
例如距离2和“辅助”，n=4，d=2，N=2*4-1=7，组合数为7!/(5!*2!) = 7 * 6 / 2 = 21。
我们可以这样组合：
def computeCombinations(n: Int, d: Int): List[List[Int]] = {
def gen(d: Int, l: List[Int]): List[List[Int]] = d match {
case 0 => List(List())
case _ => for(el <- l;
sl <- gen(d-1, l.dropWhile(_ != el).tail))
yield el :: sl
}
gen(d, (0 until n).toList)
}
这将返回要更改的字母/空格列表列表。我们通过要切换的位数来指示哪个字母或空格需要更改。为简化起见，我们假设大写的二进制数和空格/无空格的二进制数连接在一个二进制数中。
接下来，我们必须找到一种方法来从这些信息中产生变化。大写/小写很简单，假设我们收到不带空格的单词：
def toggleCharCase(c: Char) = (c ^ ('A' ^ 'a')).toChar
def toggleCases(s: String, bits: List[Int]) = (
s.zipWithIndex
map (t => if (Set(bits: _*) contains t._2) (toggleCharCase(t._1), t._2) else t)
map (_._1)
)
切换空间更加困难。我们将使用上面定义的spacesToBinary，将其转换为设置的位数列表，切换请求的位并返回。之后，我们使用不同的函数在适当的位置插入空格：
def toggleSpaces(s: String, bits: List[Int]): List[Int] = {
val before = spacesToBinary(s)
val beforeBits = Set() ++
(for(i <- 0 to 30; // Assuming 32 bits, 1 for sign
if (scala.Math.pow(2, i).toInt & before) != 0)
yield i)
val afterBits = (beforeBits union Set(bits: _*)) diff
(beforeBits intersect Set(bits : _*))
afterBits.toList
}
def addSpaces(s: String, bits: List[Int]): String = (
s.filter(_ != ' ').zipWithIndex
map (t => t._1.toString + (if (bits contains t._2) " " else ""))
mkString
)
现在我们必须计算空间差异，删除空间，切换案例，然后添加空间。让我们来看看：
def changeCombination(s: String, n: Int, bits: List[Int]) = {
// Split the binary number with all changes into case changes and space changes
val spaceBits = bits filter (_ >= n) map (_ - n)
val caseBits = bits filter (_ < n)
// Compute the set of spaces after changing them
val newSpaces = toggleSpaces(s, spaceBits)
// Remove spaces and toggle case
val noSpaces = s filter (_ != ' ')
val caseChanged = toggleCases(noSpaces, caseBits).mkString
// Now add the spaces as computed before
val spacesAdded = addSpaces(caseChanged, newSpaces).mkString
spacesAdded
}
最后，我们计算所有组合，然后为每个组合生成一个修改后的字符串：
def makeCombinations(s: String, d: Int) = {
val n = (s filter (_ != ' ')).length
for(combination <- computeCombinations(n*2-1, d))
yield changeCombination(s, n, combination)
}
这段代码已经在 Scala 2.8 上测试过了（除了我刚刚做的一些重命名）。这是运行的结果：
scala> makeCombinations("ai ds", 2) foreach println
AI ds
Ai Ds
Ai dS
A i ds
Aids
Ai d s
aI Ds
aI dS
a I ds
aIds
aI d s
ai DS
a i Ds
aiDs
ai D s
a i dS
aidS
ai d S
a ids
a i d s
aid s