Stack overflow lors du calcul des permutations d'une chaîne

Version imprimable

bonjour

la méthode permutations2 devrait renvoyer toutes les permutations d'une string, mais j'ai une stack overflow error: (pour info la méthode permutations3 marche mais que avec des chaînes ne comportant pas de caractères répétés)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 implicit class utils(val chaîne: String) {
 
        def permutations2: Seq[String] =
        {
            if(chaîne.size == 1)
                Seq(chaîne);
            else
                chaîne.zipWithIndex.flatMap{case (x:Char,i:Int) => chaîne.drop(i).permutations2.map(x +_)}
 
        }
 
 
        def permutations3 : Seq[String] =
        {
            if(chaîne.size == 1)
                Seq(chaîne)
            else
                chaîne.flatMap(x => chaîne.filterNot(_ == x).permutations3.map(x +));
        }
    }

pouvez-vous m'aider?

09/09/2013, 22h42
joel.drigo

Salut,

j'y connais rien en scala, mais une stack overflow, c'est quand on fait un appel récursif "infini" : lorsque la stack java est pleine, on a l'overflow.
09/09/2013, 22h45
gorgonite

Es-tu sûr de l'emplacement ton flatMap ?

Citation:

Envoyé par joel.drigo

j'y connais rien en scala, mais une stack overflow, c'est quand on fait un appel récursif "infini" : lorsque la stack java est pleine, on a l'overflow.

tu voudrais un <= 1 au lieu du == 1 ?

A priori, la partie en rouge ne contient pas d'appel récursif, comment va-t-elle faire un stack overflow ?

Au passage, as-tu un exemple d'argument employé ?
Sais-tu que la JVM n'a pas de quoi gérer des tail-call et que le compilateur scala ne sait pas toujours (pas souvent ^^) fabriquer une boucle à partir d'une définition récursive ?
10/09/2013, 19h23
sjrd

La méthode

Code:

drop(i)

ne fait pas ce que tu penses. Elle supprime les i premiers éléments de la chaîne, au lieu de retirer uniquement l'élément d'indice i. En fait la méthode que tu cherches n'existe pas, je crois. Mais tu peux utiliser substring :

Code:

(chaîne.substring(0, i) + chaîne.substring(i+1)).permutations2.map(x + _)

La raison pour laquelle ton code fait une stack overflow est la suivante : puisque drop(i) retire tous les i premiers éléments, lorsque i vaut 0, elle ne retire rien. chaîne.drop(0) == chaîne. Donc tu te rappelles récursivement avec la même chaîne, et ça n'en finit pas !

PS : ça sent le devoir, donc c'est probablement interdit, mais si jamais il existe aussi la méthode... permutations ^^

PS 2 : l'accent circonflexe dans chaîne, pour un identificateur, c'est quand même bof bof...

PS 3 : mets une majuscule à ta classe Utils, et fais-la "extends AnyVal" pour éviter les créations d'instances inutiles.

Voir aussi :
http://www.scala-lang.org/api/curren...able.StringOps