4

让我们考虑生成一个随机数序列的问题，约束是最终序列应该有一个固定的长度n，并且前面/后面的元素应该不同（即邻居应该不同）。我的第一个惯用方法是：

val seq = Stream.continually{ Random.nextInt(10) }
                .foldLeft(Stream[Int]()){ (all: Stream[Int], next: Int) =>
                  if (all.length > 0 && all.last != next)
                    all :+ next
                  else
                    all
                }
                .take(n)

不幸的是，这不起作用，因为 foldLeft 试图消耗整个无限流，从而导致无限循环。直观地根据这个问题，我预计这种行为仅适​​用于使用foldRight? 也许我只是错过了另一个惯用的解决方案？

4

4 回答 4

4

您可以使用该技巧与自身压缩流：

def randSeq(n: Int): Stream[Int] = {
  // an infinite stream of random numbers
  val s = Stream.continually{ Random.nextInt(10) }
  s.zip(s.tail) // pair each number with it sucessor
   .filter((pair) => pair._1 != pair._2) // filter out equal pairs
   .map(_._1)   // break pairs again
   .take(n);    // take first n
}

然后你可以过滤掉连续相等的元素，最后取所需的数量。

更新：是的，它会工作。假设你有[1,2,2,2,3,...]. 压缩它会导致[(1,2),(2,2),(2,2),(2,3),(3,..),...]，过滤产生[(1,2),(2,3),(3,..),...]所以最终的结果是[1,2,3,...]。

我们甚至可以证明：配对后，序列具有如下性质：a(i)._2 = a(i+1)._1. 此属性在过滤步骤中保留。过滤步骤还确保a(i)._1 != a(i)._2. 放在一起，我们a(i)._1 != a(i)._2 = a(i+1)._1确实得到了这样的结果a(i)._1 != a(i+1)._1。

您使用的方法的问题fold是您在 fold 函数中自下而上地构建 Stream 。这意味着为了评估流的头部，您必须评估无限的:+操作序列，即使头部保持不变。必须自上而下地构建适当的流 - 计算其头部并将其余部分的计算推迟到其尾部。例如：

def randSeq1(n: Int): Stream[Int] = {
  def g(s: Stream[Int]): Stream[Int] =
    s match {
      case h #:: t => h #:: g(t.dropWhile(_ == h))
    }
  g(Stream.continually{ Random.nextInt(10) }).take(n);
}

在这里，我们首先发出头部并将其余的计算推迟到延迟评估的尾部。

于 2013-07-01T12:03:35.297 回答
1

那么，这个怎么样：

scala> val M = 10
M: Int = 10

scala> val seq = Stream.iterate(Random.nextInt(M)){ x => 
         val nxt = Random.nextInt(M-1); if(nxt >= x) nxt + 1 else nxt 
       }
于 2013-07-01T14:18:08.667 回答
1

虽然用自己的头部压缩流是一个非常好的技巧，但我更喜欢sliding运算符：

val s = Stream.continually { Random.nextInt(10) } sliding(2) collect { case Stream(a,b) if a!=b => a } take 100

当心：你会得到一个迭代器，而不是一个流。Stream 会记住它的结果（因此可以多次迭代）。一个迭代器可能只能迭代一次。

于 2013-07-01T13:43:07.077 回答
1

我还没有检查它，但我希望你能明白：

@annotation.tailrec 
def rndDistinctItems(n: Int, xs: List[Int] = Nil): List[Int] = if (n > 0) {
    val next = Random.nextInt(10)
    val shouldTryAgain = xs != Nil && next == xs.head
    if (shouldTryAgain) rndDistinctItems(n, xs)
    else rndDistinctItems(n - 1, next::xs)
} else xs
于 2013-07-01T11:50:21.913 回答