首页 文章

摘要在重复的flatMap

提问于
浏览 次
13

我试图概括重复，嵌套 flatMap 但不确定是否存在 .

以下代码将生成n选择3，
n choose 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，
n choose 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，
n choose 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不支持，我对此感兴趣 .

Edit: 他是一个示例调用者，并按请求生成输出：

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），列表（0,2,4），列表（0,3,4），列表（1,2,3），列表（1,2,4），列表（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）

它只提供从0开始的包含n个元素的整数集的所有r元素子集 . More information on combinations can be found on Wikipedia .

scala functional-programming higher-order-functions

1 回答

  • 12

    这是一种看待这个问题的方法，我想出了这个方法 .

    您可以在链中提取一个阶段作为函数 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]] ，它是内形的（具有相同的参数和返回类型） .

    对于内部kleisli箭头有一个monoid实例，其中monoid "addition"表示 flatMap 操作（或伪代码， f1 |+| f2 == a => f1(a).flatMap(f2) ） . 因此，要替换 flatMap 的"add"实例，或者换句话说，将 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]] ：你不希望所有的组合都缓存在内存中），但这是留给读者的练习 .

    回复于

相关问题