Вернуть список пар вращательной эквивалентности из заданной строки в Scala

Question

Входная строка

["ac", "bd", "ce", "aaa", "xyz", "bbb", "abc", "kt", "zb"]

Я хочу следующий вывод:

[List ("ac", "bd", "ce", "zb"), List ("aaa"), "bbb"), List ("abc", "xyz"), List ("kt")]

Логика заключается в том, что мне нужно сгруппировать подобные элементы в списки.

Шаблон в первом списке: у меня пропущена одна буква.

Шаблон во втором списке: у меня одна буква, повторяющаяся трижды.

Шаблон в третьем списке, У меня есть 3 последовательных буквы.

После группировки всего этого у меня есть один элемент, который не попадает ни в один из вышеуказанных шаблонов, поэтому я добавляю его в отдельный список.

Я не являюсьуверен в алгоритме / решении в Scala.Любая помощь приветствуется.ТИА.

Answer 1

Методы, которые создают представление эквивалентности вращения строк.

  def normalizedRepresentation(str: String) = {
    str.map(char => (char - str.charAt(0) + 'a').asInstanceOf[Char])
  }

  def rotationalEquivalenceRepresentation(str: String) = {
    val normalizedStr = normalizedRepresentation(str)
    normalizedStr.map(char => if (char < 'a') (char + 26).asInstanceOf[Char] else char.asInstanceOf[Char])
  }

затем

scala>   val input = List("ac","bd","ce", "aaa","xyz","bbb","abc","kt","zb")
input: List[String] = List(ac, bd, ce, aaa, xyz, bbb, abc, kt, zb)

scala>   input.map(str => normalizedRepresentation(str))
res0: List[String] = List(ac, ac, ac, aaa, abc, aaa, abc, aj, aI)

scala>   input.map(str => rotationalEquivalenceRepresentation(str))
res1: List[String] = List(ac, ac, ac, aaa, abc, aaa, abc, aj, ac)

scala> 

scala>   input.groupBy(str => rotationalEquivalenceRepresentation(str))
res2: scala.collection.immutable.Map[String,List[String]] = Map(abc -> List(xyz, abc), aaa -> List(aaa, bbb), ac -> List(ac, bd, ce, zb), aj -> List(kt))

scala>   input.groupBy(str => rotationalEquivalenceRepresentation(str)).values.toList
res3: List[List[String]] = List(List(xyz, abc), List(aaa, bbb), List(ac, bd, ce, zb), List(kt))

Answer 2

Вот общее решение вопроса.

def rotationGroup(s: String) =
  s.sliding(2).toList.map(s => ('a' + s(1) - s(0)) % 26)

list.groupBy(rotationGroup).values

Он работает, вычисляя расстояние между парой букв и затем представляя «группу вращения» в виде списка расстояний между каждой соседней парой встрока.

Это аннотированная версия функции с проверкой ошибок:

def rotationGroup(s: String) =
  s
    .sliding(2) // Group letters into pairs
    .filter(_.length > 1) // Avoid strings with 0 or 1 letters
    .map(s => ('a' + s(1) - s(0)) % 26) // Compute modulo distance between letters
    .toList // Convert from an iterator to a concrete list

Answer 3

Похоже, довольно бессмысленное упражнение.

val input = List("ac","bd","ce", "aaa","xyz","bbb","abc","kt","zb")

val (skip1, rest1) =
  input.partition(s => s.length == 2 && s(1)-s(0) == 2 || s(0)-s(1) == 24)
//skip1: List[String] = List(ac, bd, ce, zb)
//rest1: List[String] = List(aaa, xyz, bbb, abc, kt)

val (same3, rest2) =
  rest1.partition(s => s.length == 3 && s.forall(_ == s(0)))
//same3: List[String] = List(aaa, bbb)
//rest2: List[String] = List(xyz, abc, kt)

val (seq3, rest3) =
  rest2.partition(s => s.length == 3 && s(1)-s(0) == 1 && s(2)-s(1) == 1)
//seq3: List[String] = List(xyz, abc)
//rest3: List[String] = List(kt)