string - 在Scala中计算排列或字符串时堆栈溢出

Question

全部在标题中，代码在这里：

implicit class utils(val chaîne: String) {

    def permutations1(): List[String] = {
        if (chaîne.length() == 0) List()
        else
        if (chaîne.length() == 1) List(chaîne)
        else  {
            val retour1=for {i:Int <- 0 to chaîne.length() - 2
                 chaîne_réduite = chaîne.drop(i)
                 liste_avec_chaîne_réduite = chaîne_réduite.permutations1()
                 une_chaîne_réduite_et_permutée <- liste_avec_chaîne_réduite
                 j <- 0 to une_chaîne_réduite_et_permutée.length()
            }
            yield new StringBuilder(une_chaîne_réduite_et_permutée).insert(j, chaîne(j)).toString

            retour1.toList
        }
    }
}

你能解释一下为什么它不起作用并最终纠正我的代码以使其避免堆栈溢出吗？

Answer 1

我自己找到了答案：

implicit class utils (val chaîne: String) {
  def permutations1 : Seq [String] = {
    if (chaîne.size == 1) Seq (chaîne)
    else chaîne.flatMap (x => chaîne.filterNot (_ == x).permutations1.map (x + _))
  }
}

Answer 2

问题不是NP-complete吗？因此，您只能运行字符串长度非常有限的任何代码。

为了使其在合理的字符串长度上工作，需要仔细优化。例如，为了提高性能，您可以尝试@tailrec优化。

String以和的形式表示StringBuilder对于任务来说是非常低效的。例如尝试List。Char