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

問題はNP完全ではありませんか？したがって、文字列の長さが非常に制限されたコードのみを実行できます。

合理的な文字列長で機能させるには、慎重な最適化が必要です。たとえば、パフォーマンスを向上させるために、@tailrec最適化を試みることができます。

Stringandの形式での表現は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 + _))
  }
}