Как получить все возможные разделы для списка в Scala - PullRequest
Новая
       19

Как получить все возможные разделы для списка в Scala

1 голос
/ 18 марта 2019

У меня есть список строк, например, List("A", "B", "C"). Я хотел бы получить все возможные разделы этого в Scala. Результат, который я ожидаю: 

def func(List[String]): List[List[String]] = {
// some operations
}
In: func(List("A", "B", "C"))
Out: 
[
[["A"], ["B"], ["C"]], 
[["A", "B"], ["C"]], 
[["A", "C"], ["B"]], 
[["B", "C"], ["A"]], 
[["A", "B", "C"]], 
]

1 Ответ

0 голосов
/ 18 марта 2019

Это решение с использованием Set: 

def partitions[T](seq: TraversableOnce[T]): Set[Set[Set[T]]] = {
  def loop(set: Set[T]): Set[Set[Set[T]]] =
    if (set.size < 2) {
      Set(Set(set))
    } else {
      set.subsets.filter(_.nonEmpty).flatMap(sub =>
        loop(set -- sub).map(_ + sub - Set.empty)
      ).toSet
    }

  loop(seq.toSet)
}

Использование Set упрощает логику, но удаляет повторяющиеся значения, если они присутствуют в исходном списке.Та же логика может быть использована для List, но вам необходимо реализовать операции, подобные множеству, такие как subsets.

Просто для справки, вот реализация, использующая List, которая сохранитдубликаты в списке ввода. 

def partitions[T](list: List[T]): List[List[List[T]]] =
  list match {
    case Nil | _ :: Nil => // 0/1 elements
      List(List(list))
    case head :: tail => // 2+ elements
      partitions(tail).flatMap(part => {
        val joins =
          part.indices.map(i =>
            part.zipWithIndex.map { case (p, j) =>
              if (i == j) {
                head +: p
              } else {
                p
              }
            }
          )

        (List(head) +: part) +: joins
      })
  }
...