在重复使用flatMap时进行抽象化

Question

我正在尝试泛化重复的、嵌套的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 允许我使用 for 表达式重写 map/flatMap，这样读起来更清晰，但选择的数量仍然是硬编码的。

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到 n).combinations(r)来使用库提供的计算组合的实现。

虽然上面的代码是Scala，但在这种情况下，我对其功能编程方面感兴趣，而不是语言能力。 如果有解决方案，但不受Scala支持，我也感兴趣。

编辑：他是一个样本调用者，并按要求输出相应的输出：

```scala scala > combinationsRecursiveLoop(5, 3) res0: Seq[Seq[Int]] = Vector(List(0, 1, 2), List(0, 1, 3), List(0, 1, 4), List(0, 2, 3), List(0, 2, 4), List(0, 3, 4), List(1, 2, 3), List(1, 2, 4), List(1, 3, 4), List(2, 3, 4))

scala > combinationsRecursiveLoop(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) ```

这段代码是关于Scala编程语言中组合问题的解决方案。第一行代码实现返回长度为3的从0到4的排列组合，第二行代码则将结果转换成了字符串格式方便输出显示。

它只是提供了从零开始包含n个元素的整数集的所有r元素子集。关于组合的更多信息可以在维基百科上找到。

- vossad01

---

你能否添加一些客户端代码调用你的函数和期望输出的示例？对于我来说，你试图实现什么并不清楚。 - andyczerwonka

我认为那些递归函数是做这种事情的“标准”方式。 - Jasper-M

非常有趣的问题，但我认为递归通常是嵌套、重复行为的答案。我真的希望被证明是错误的！ - evan.oman

这个结构（曾经）被称为 power loop :-) - Bergi

Answer 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箭头Kleisli[List, List[Int], List[Int]]，它是内态的（具有相同的参数和返回类型）。

对于内态的Kleisli箭头，存在幺半群实例，其中幺半群“加法”表示flatMap操作（或者在伪代码中，f1 |+| f2 == a => f1(a).flatMap(f2)）。因此，要替换您的flatMap链，您需要“添加”此f函数的r个实例，换句话说，将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]]: 您不希望所有组合都缓存在内存中），但这留给读者自己练习。

- Kolmar