Реферат по многократной карте

Я пытаюсь обобщить повторяющийся, вложенный flatMap, но не уверен, что он существует.

В следующем коде будут созданы все комбинации n, выбираем 3, :

def choose3flatMap(n: Int, r: Int = 3) =
  (0 to n - r)
    .flatMap(i => (i + 1 to n - (r - 1))
      .flatMap(j => (j + 1 to n - (r - 2))
        .map(k => Seq(i, j, k))))

Повторяя операцию flatMap, мы можем получить все комбинации n, выбираем 5, :

def choose5flatMap(n: Int, r: Int = 5) =
  (0 to n - r)
    .flatMap(i => (i + 1 to n - (r - 1))
      .flatMap(j => (j + 1 to n - (r - 2))
        .flatMap(k => (k + 1 to n - (r - 3))
          .flatMap(l => (l + 1 to n - (r - 4))
            .map(m => Seq(i, j, k, l, m)))))

Ясно, что здесь есть шаблон. Я хотел бы использовать это сходство, чтобы получить общее решение для n выбрать r, . Есть ли простой способ достичь этого. Возможно, какая-то функция более высокого порядка?

То, что я пробовал:

Scala позволяет мне переписать map/flatMap с помощью выражения for. Это считывает очиститель, но количество вариантов по-прежнему жестко закодировано.

def choose3Loop(n: Int, r: Int = 3) =
  for {
    i <- 0 to n - r
    j <- i + 1 to n - (r - 1)
    k <- j + 1 to n - (r - 2)
  } yield Seq(i, j, k)

Я могу написать рекурсивное решение непосредственно с помощью flatMap или с использованием сахара выражения for:

def combinationsRecursive(n: Int, r: Int, i: Int = 0): Seq[Seq[Int]] =
  if (r == 1) (i until n).map(Seq(_))
  else {
    (i to n - r).flatMap(
      i => combinationsRecursive(n, r - 1, i + 1).map(j => i +: j))
  }

def combinationsRecursiveLoop(n: Int, r: Int, i: Int = 0): Seq[Seq[Int]] =
  if (r == 1) (i until n).map(Seq(_))
  else
    for {
      i <- i to n - r
      j <- combinationsRecursiveLoop(n, r - 1, i + 1)
    } yield i +: j

Хотя это решения общей проблемы, я задаюсь вопросом, есть ли абстракция более высокого уровня, которую я здесь отсутствует, что может быть применимо и к другим проблемам. Я признаю, что для этого конкретного приложения я мог бы сделать (0 to n).combinations(r), чтобы использовать библиотечную реализацию комбинаций вычислений.

В то время как вышеприведенный код Scala, в этом случае меня интересует его функциональный аспект, а не возможности языка. Если есть решение, но которое не поддерживается Scala, меня это интересует.

Изменить: Он является образцом для вызова и результирующий вывод по запросу:

scala > combinationRecursiveLoop (5, 3)

res0: Seq [Seq [Int]] = Вектор (список (0, 1, 2), список (0, 1, 3), список (0, 1, 4), список (0, 2, 3), Список (0, 2, 4), Список (0, 3, 4), Список (1, 2, 3), Список (1, 2, 4), Список (1, 3, 4), Список (2, 3, 4))

scala > combinationRecursiveLoop (5, 3).map( "(" + _. mkString ( "," ) + ")" ). mkString ("")

res1: String = (0, 1, 2) (0, 1, 3) (0, 1, 4) (0, 2, 3) (0, 2, 4) (0, 3, 4) 1, 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4)

Он просто предоставляет все подмножества r-элементов набора целых чисел, начиная с нуля, содержащего n элементов. Подробнее о комбинациях можно найти в Википедии.

Ответ 1

Вот один из способов взглянуть на это, что я придумал.

Вы можете выделить один этап в своей цепочке как функцию f: List[Int] => List[List[Int]], которая принимает List с началом комбинации и добавляет к ней все возможные последующие элементы.

Например, в choose(5, 3), f(List(2, 0)) приведет к List(List(3, 2, 0), List(4, 2, 0)).

Вот возможная реализация такой функции с некоторой обработкой для исходного добавляемого случая:

val f: List[Int] => List[List[Int]] = l =>
  (l.headOption.map(_ + 1).getOrElse(0) to n - (r - l.size))
    .map(_ :: l).toList

Теперь такая функция Kleisli arrow Kleisli[List, List[Int], List[Int]], и она эндоморфна (имеет те же аргументы и возвращаемые типы).

Существует экземпляр monoid для эндоморфных стрелок kleisli, где моноидное "сложение" означает операцию flatMap (или в псевдокоде, f1 |+| f2 == a => f1(a).flatMap(f2)). Чтобы заменить цепочку flatMap, вам нужно "добавить" r экземпляры этой функции f или, другими словами, для умножения функции f на r.

Эта идея переводится непосредственно в код Scalaz:

import scalaz._, Scalaz._

def choose(n: Int, r: Int) = {
  val f: List[Int] => List[List[Int]] = l =>
    (l.headOption.map(_ + 1).getOrElse(0) to n - (r - l.size))
      .map(_ :: l).toList
  Endomorphic.endoKleisli(f).multiply(r).run(Nil)
}

И вот пример его запуска:

scala> choose(4, 3)
res1: List[List[Int]] = List(List(2, 1, 0), List(3, 1, 0), List(3, 2, 0), List(3, 2, 1))

Комбинации обращаются вспять, но должно быть возможно сделать версию, которая производит комбинации с элементами в возрастающем порядке (или просто запускает choose(n, r).map(_.reverse)).

Еще одно усовершенствование - сделать ленивую версию, которая возвращает Stream[List[Int]] (или даже лучше scalaz.EphemeralStream[List[Int]]): вы не хотите, чтобы все комбинации были кешированы в памяти), но это остается как упражнение для читатель.