Комбинаторика: группировка проблем символов

Вычислить количество комбинаций несложно. По сути, между каждыми двумя буквами стоит символ. Это может быть «эпсилон» (пустой) или пробел. Итак, для 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 * п -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 (слово) вернет двоичное число, представляющее пробелы в этом слове. Например, он вернет «010» для «ai ds» и «111» для «help s». Количество изменений между каждой комбинацией определяется путем XOR результатов f (010 xor 111 = 101), а затем подсчета количества битов, равного 1. Пусть ' s напишите пару функций на 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)

Последний критерий i известен как неравенство треугольника. Проще говоря, путь от x до z по крайней мере такой же мал, как путь от x до y плюс путь от y до z (представьте себе треугольник с вершинами x, y и z).

Хорошо, давайте подумаем о бонусные вопросы.

Сколько путей между двумя словами? Что ж, если расстояние Левенштейна равно n, это означает, что у вас есть «n» уникальных модификаций, a1, a2, ..., an. Для каждого порядка этих модификаций у вас есть путь. Количество перестановок " представляющие пробелы и заглавные буквы каждой буквы, первая из которых состоит из 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)
)

Переключение пробелов сложнее. Мы воспользуемся пространством spaceToBinary, определенным выше, преобразуем его в список установленных номеров битов, переключим запрошенные биты и вернем их. После этого мы используем другую функцию для вставки пробелов в нужные места:

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