在 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

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

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

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

Answer 2

我自己找到了答案：

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 + _))
  }
}