Блог

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

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

#scala #list #combinations

#scala #Список #комбинации

Вопрос:

У меня есть список строк, например 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. Как вы хотите обрабатывать повторяющиеся значения, т.е. List("A","B","A") ?

2. Не могли бы вы, пожалуйста, подробнее объяснить, когда вы говорите «разделы для списка»?

3. Подпись вашей функции кажется неверной. Разве результат не должен быть List[List[List[String]]] ?

4. Вы ищете набор мощности

Ответ №1:

Это решение, использующее 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
      })
  }