在Scala中计算排列或字符串时发生堆栈溢出
在Scala中计算排列或字符串时发生堆栈溢出
提问于 2013-09-09 02:26:28
所有内容都在标题中，代码如下：
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
}
}
}你能解释为什么它不工作，并最终更正我的代码，使其避免堆栈溢出吗？
回答 2
Stack Overflow用户
发布于 2013-09-09 03:04:12
难道不是NP-complete的问题吗？因此，您只能运行字符串长度非常有限的任何代码。
要使其在合理的字符串长度上工作，需要仔细优化。例如，要提高性能，您可以尝试@tailrec优化。
以String和StringBuilder的形式表示对于任务来说是非常低效的。例如，尝试使用Char的List。
Stack Overflow用户
发布于 2013-09-09 04:53:14
我自己找到了答案：
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 + _))
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/18687160
复制相关文章
相似问题
腾讯云开发者
