Вычисление количества комбинаций тривиально. По сути, у вас есть символ между каждыми двумя буквами. Это может быть «эпсилон» (пустой) или пробел. Итак, для n букв у вас n-1 таких символов-разделителей. Поскольку каждый символ может иметь только два значения, это то же самое, что двоичное число из n-1 цифр. Таким образом, вы можете иметь 2 в степени n-1 комбинаций.
aids = 4 characters (n = 4)
n - 1 = 3
2 ** (n-1) = 8 combinations
Теперь для особых случаев. Если каждый символ может быть в нижнем или верхнем регистре, то это 2 степени n вариаций для символов (если они являются буквами). Теперь каждая вышеприведенная комбинация имеет 2 n вариаций в зависимости от капитализации, поэтому конечный результат равен (2 (n-1)) * (2 ** n), что равно 2 ** (2 * n -1).
Для каждого дополнительного письма вы удваиваете или удваиваете (в зависимости от заглавных букв) время, необходимое для их перечисления, как легко понять из формулы.
Общее количество символов немного сложнее, но достаточно заметить, что каждый "пробел" равен "эпсилону" наполовину. Таким образом, мы имеем (2 ** (n-1)) * n (буквы) + ((2 ** (n-1)) * (n-1)) / 2 (пробелы). В примере:
(2 ** 3) * 4 = 32 characters
(2 ** 3) * 3 / 2 = 12 spaces
Total = 44 characters
Наконец, проблема расстояния связана с расстоянием Левенштейна . Я думал об использовании дерева Буркхарда-Келлера , но теперь я вижу, что в этом нет необходимости, поскольку проблема довольно проста.
Во-первых, минимальное количество вставок / удалений / изменений, необходимое для того, чтобы сделать одну строку равной другой, называется расстоянием Левенштейна . Это непосредственно относится к проблеме: вы добавляете пробелы, удаляете пробелы, меняете строчные / прописные буквы по мере необходимости. Обычно это лучше всего решить с помощью Динамического программирования , которое обычно можно рассматривать как хранение данных о решении небольших частей проблемы, которые затем повторно используются для вычисления других частей / больших частей.
Но, учитывая конкретные ограничения нашей задачи, мы можем просто сравнить «двоичные» числа, представляющие пробелы / эпсилон.
Скажем, функция f (word) вернет двоичное число, представляющее пробелы в этом слове. Например, он вернет «010» для «ai ds» и «111» для «a i d s». Число изменений между каждой комбинацией задается путем XOR для результатов 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)}
}
Итак, расстояние Левенштейна:
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).
Хорошо, давайте подумаем о бонусных вопросах.
Сколько путей существует между двумя словами? Что ж, если расстояние Левенштейна равно 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 букв существует одна и только одна соответствующая комбинация, так что расстояние Левенштейна между этими двумя комбинациями составляет 2 * n - 1, максимально возможное расстояние между любыми двумя комбинации.
Вижу, я забыл вычислить все комбинации, чье (минимальное) расстояние до s равно n. Итак, мы знаем, что каждая комбинация может быть представлена в виде двух двоичных чисел, представляющих пробелы и заглавные буквы каждой буквы, первая из которых имеет длину n-1 цифр, а вторая длиной n цифр.
Мы также знаем, что мы можем просто инвертировать любую из этих «цифр», чтобы получить разницу. Таким образом, если мы получаем одно большое двоичное число длиной 2 * n - 1 цифра и перечисляем все его цифры, комбинации на минимальном расстоянии d от него задаются комбинацией 2 * n-1 цифр в группах размера «д» без повторений. Для N = 2 * n-1 число таких комбинаций равно N! / ((N-d)! * 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)
)
Пространство переключения сложнее. Мы будем использовать определенные выше пробелы, преобразуем их в список установленных битовых чисел, переключаем запрошенные биты и возвращаем их. После этого мы используем другую функцию для вставки пробелов в нужных местах:
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