in-shuffle 的尾递归实现

Question

我对 In_Shuffle 传递给方法的列表使用递归，但与递归基本情况混淆了。由于 Scala 不允许您修改传递的参数，因此我无法为传递的列表分配新值。这是我的代码：

def shuffle(list1: List[Any], list2: List[Any]): List[Any] = {
    list1.zipAll(list2, "", "")
      .flatMap(_.productIterator.toList)
      .filter(_ != "")
  }

def splitLists(list: List[Any], n: Int) = {
    if (n > list.length) {
      throw new Exception("N is greater than length of list")
    }
    else if (n == list.length) {
      List(list, List())
    }
    else {
      List(list.slice(0, n),
        list.slice(n, list.length))
    }
  }

以下方法处于无限循环中。我知道问题出在我初始化 list 变量的第一行。

  @annotation.tailrec
  def in_shuffle(list:List[Any], org_list:List[Any]):Any={
    var list:List[Any] = List()
    if (list.equals(org_list)) return true
    if (list.length<1) {
      list=org_list
    }
    val div_list = splitLists(list, list.length/2)
    list = shuffle(div_list(0), div_list(1))
    in_shuffle(list, org_list)
  }

In-Shuffle 正在使用以下代码调用。

println(in_shuffle(List(), (1 to 4).toList))
任何帮助将不胜感激。谢谢。

Answer 1

您的代码几乎没有问题。我们尽量避免 Any 而不是

def shuffle(list1: List[Any], list2: List[Any]): List[Any]

我们使用类型参数T

def shuffle(t: (List[T], List[T])): List[T]

接下来我们flatten a list of tuples这样

def shuffle(t: (List[T], List[T])): List[T] =
  t._2 zip t._1 flatMap { case (a, b) => List(a, b) }

接下来我们使用开箱即用的 splitAt 而不是滚动我们自己的 splitLists

val (left, right) = list.splitAt(list.size/2)

最后我们避免使用return。把它们放在一起我们有

def in_shuffle[T](original: List[T]) = {
  require(original.size % 2 == 0, "In shuffle requires even number of elements")

  def shuffle(t: (List[T], List[T])): List[T] =
    t._2 zip t._1 flatMap { case (a, b) => List(a, b) }

  def midpoint(l: List[T]): Int = l.size / 2

  @annotation.tailrec def loop(current: List[T]): Boolean = {
    if (original == current) true
    else loop(shuffle(current.splitAt(midpoint(current))))
  }

  loop(shuffle(original.splitAt(midpoint(original))))
}

in_shuffle((1 to 52).toList)   // res0: Boolean = true

注意in shuffle要求元素个数为偶数。

in-shuffle 的尾递归实现

Tail-recursive implementation of in-shuffle

scala

recursion

shuffle

tail-recursion