摘要在重复的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 to n).combinations(r)使用库提供的计算组合实现.

虽然上面的代码是Scala,但在这种情况下,我感兴趣的是它的函数式编程方面,而不是语言功能.如果有一个解决方案,但Scala不支持,我对此感兴趣.

编辑: 他是一个示例调用者和请求的结果输出:

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

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

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箭头有一个monoid实例,其中monoid"加法"表示flatMap操作(或伪代码f1 |+| f2 == a => f1(a).flatMap(f2)).因此,要替换您的flatMaps 链,您需要"添加" 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]]:你不希望所有的组合都缓存在内存中),但这是留给读者的练习.