組み合わせの数を計算するのは簡単です。基本的に、2つの文字の間に文字があります。「イプシロン」（空）またはスペースの場合があります。したがって、n文字の場合、そのような区切り文字はn-1個あります。各文字は2つの値しか持てないため、n-1桁の2進数と同じです。したがって、2のn-1の組み合わせの累乗を持つことができます。
aids = 4 characters (n = 4)
n - 1 = 3
2 ** (n-1) = 8 combinations
さて、特別な場合のために。各文字が小文字または大文字のいずれかである場合、それは文字のnのバリエーションの2の累乗です（文字である限り）。ここで、上記の各組み合わせには、大文字と小文字の区別に基づいて2 nのバリエーションがあるため、最終結果は（2（n-1））*（2 ** n）になり、これは2 **（2 * n -1）に等しくなります。
数式から簡単に理解できるように、追加の文字ごとに、それらを列挙するのにかかる時間は2倍または4倍になります（大文字化の内容によって異なります）。
文字の総数は少し難しいですが、各「スペース」が半分の時間「イプシロン」であることに注意してください。したがって、（2 **（n-1））* n（文字）+（（2 **（n-1））*（n-1））/ 2（スペース）があります。例では：
(2 ** 3) * 4 = 32 characters
(2 ** 3) * 3 / 2 = 12 spaces
Total = 44 characters
最後に、距離の問題はレーベンシュタイン距離に関連しています。Burkhard-Kellerツリーを使用することを考えましたが、問題がかなり単純であるため、これはまったく必要ないことがわかりました。
まず、ある文字列を別の文字列と等しくするために必要な挿入/削除/変更の最小数は、レーベンシュタイン距離と呼ばれます。これは問題に直接当てはまります。必要に応じて、スペースを追加したり、スペースを削除したり、小文字/大文字を変更したりします。通常、これは動的計画法で最もよく解決されます。動的計画法は、一般に、問題の小さな部分の解決策に関するデータを保持し、他の部分/大きな部分の計算に再利用されると考えることができます。
しかし、私たちの問題の特定の制限を考えると、スペース/イプシロンを表す「2進数」を比較することができます。
関数f（word）が、その単語のスペースを表す2進数を返すとします。たとえば、「ai ds」の場合は「010」、「aids」の場合は「111」を返します。各組み合わせ間の変更の数は、f（010 xor 111 = 101）の結果をXORし、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)}
}
したがって、レーベンシュタイン距離は次のようになります。
def levenshtein(s1: String, s2: String) = spaceDistance(s1, s2) + caseDistance(s1, s2)
レーベンシュタイン距離については、次の特性もわかっています。d（x、y）は、xとyの間のレーベンシュタイン距離です。次に、私たちは知っています：
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を持つ三角形を考えてください）。
では、ボーナスの質問について考えてみましょう。
2つの単語の間にいくつのパスがありますか？レーベンシュタイン距離が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
「中央」の組み合わせはありますか？実は違う。戻って、組み合わせをスペース/スペースなしと小文字/大文字を表す2進数のペアと考えると、ビットを単純に反転して、選択したものまでの距離が可能な限り最大。
または、言い換えると、n文字のすべての組み合わせに対して、対応する組み合わせは1つだけであるため、2つの組み合わせ間のレーベンシュタイン距離は2 * n -1であり、任意の2つの組み合わせ間の可能な最大距離です。
sまでの（最小）距離がnであるすべての組み合わせを計算するのを忘れたようです。さて、各組み合わせは2つの2進数として表すことができ、各文字のスペースと大文字を表します。最初の文字の長さはn-1桁、2番目の文字の長さはn桁です。
また、これらの「数字」のいずれかを単純に反転して、違いを得ることができることもわかっています。したがって、2 * n-1桁の長さの1つの大きな2進数を取得し、そのすべての桁を列挙すると、それから最小距離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)
}
これにより、変更する文字/スペースのリストのリストが返されます。切り替えたいビット数によって、どの文字またはスペースを変更する必要があるかを示します。簡単にするために、大文字の2進数とスペース/スペースなしの2進数が1つの2進数に連結されていると仮定します。
次に、この情報からバリエーションを生成する方法を見つける必要があります。スペースなしの単語を受け取ると仮定すると、大文字/小文字は単純です。
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)
}
このコードはすべてScala2.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