使用Scala进行游程编码 [英] Run length encoding using Scala

问题描述

给出一个元素列表，其中一些元素会重复多次，我需要使用元组生成一个新列表，其中每个元组包含一个元素连续重复一个元素的次数本身.

Given a list of elements of which some are repeated multiple times, i need to produce a new list with tuples, where each tuple contains number of times an element is repeated in a row and an element itself.

例如，给定

println(func(List()))              // should be empty list
println(func(List(1, 1)))          // (2,1) <- 1 is repeated 2 times
println(func(List(1, 1, 2, 1)))    // (2,1)(1,2)(1,1)

这是我目前最好的尝试.我觉得我缺少一些非常基本的东西，请帮助我了解什么

This is my best attempt at this point. I feel that i am missing something very basic, please help me understand what

  def func[X](xs: List[X]): List[(Int, X)] = xs match {
    case Nil => Nil
    case y :: ys   => ys match {
      case Nil     => (1, y) :: Nil
      case z :: zs => if (y != z) (ys.prefixLength(_ == ys.head), y) :: func(ys) 
                      else func(ys)
    }
  }

分析出问题所在之后，在我看来，当我递归调用func(ys)时，ys没有足够的信息来确定元素的数量.假设我们正在处理List(1,1,1,2).好的，因此y是1，z是1和(1::(2::Nil))是zs.按照我上面的逻辑，下一次调用会丢失1次2次的事实.

After analyzing what the problem is, it seems to me that at the point when i recursively call func(ys), ys does not have enough information to figure out the count of elements. Say we're dealing with List(1,1,1,2). Ok, so, y is 1, z is 1 and (1::(2::Nil)) is zs. Following my logic above, the fact that 1 was seen 2 times is lost for the next call.

问题可能是我没有以正确的方式考虑问题.我要记住的是遍历列表，直到发现该元素与先前的元素不同，此时，计算一个元素的出现次数并将其放入元组")

The problem may be that i am not thinking about the problem the right way. What i have in mind is "go along the list until you find that this element is not the same as a previous elements, at which point, count the number of occurrences of an element and make it into the tuple")

我认识到，在上述情况下(在我的代码中)，问题在于当数字实际上相同时(1,1)，我们已经看到一个数字的事实并没有反映在任何地方.但是鉴于我还没有准备好编写元组，请在哪里可以做

I recognize that in the above scenario (in my code) the problem is that when numbers are in fact the same (1,1) the fact that we already saw a number is not reflected anywhere. But where can this be done please, given that i am not yet ready to compose a tuple

在回答此问题时，请坚持使用案例结构.我意识到也许还有其他更好，更清洁的方法可以解决此问题，我想更好地了解我在这里做错了什么

In answering this question, please stick to case structure. I realize that there maybe other better, cleaner ways to address this problem, i would like to better understand what i am doing wrong here

推荐答案

您处在正确的轨道上.问题在于，您不能只在此处逐步构建结果列表，而必须从递归调用中获得列表，然后检查是否需要添加新对或增加最后一个对的数目一个:

You're on the right track. The problem is that you can't just incrementally build the result list here—you'll have to pull the head off the list you get from the recursive call and check whether you need to add a new pair or increment the count of the last one:

def func[X](xs: List[X]): List[(Int, X)] = xs match {
  case Nil => Nil
  case y :: ys => func(ys) match {
    case (c, `y`) :: rest => (c + 1, y) :: rest
    case             rest => (    1, y) :: rest
  }
}

请注意嵌套匹配模式中y周围的反引号，这对于避免仅定义一个名为y的新变量是必要的.

Note the backticks around y in the nested match pattern—this is necessary to avoid just defining a new variable named y.

这篇关于使用Scala进行游程编码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！