Хвосто-рекурсивная реализация in-shuffle - PullRequest
Новая
       33

Хвосто-рекурсивная реализация in-shuffle

0 голосов
/ 12 февраля 2020

Я использую рекурсию для 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))
    }
  }

Следующий метод бесконечен l oop. Я знаю, что проблема в самой первой строке, где я инициализирую переменную 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))
Любая помощь будет высоко оценена. Спасибо.

1 Ответ

3 голосов
/ 13 февраля 2020

Есть несколько проблем с вашим кодом. Мы стараемся избегать Any, поэтому вместо 

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

мы используем параметр типа T

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

Далее мы сглаживаем список кортежей как так 

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

Примечание в случайном порядке требует, чтобы количество элементов было четным.

...