Mélangeur de caractères

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

[sujet résolu, le code-source final est disponible dans l'OP, ainsi que les explications qui vont avec]


Salut à tous les agrumes,

J'essaie de mettre en place un mélangeur de caractères qui soit de fait capable d'afficher toutes les combinaisons possibles des caractères d'une chaîne.

CAS D'UTILISATION

On donne à ce programme une chaîne, mettons ABC.

Celui-ci affichera :

ABC - ACB - BAC - BCA - CAB - CBA (exactement dans cet ordre : on bloque les lettres)

ALGORITHME

Il est possible de créer une fonction qui soit récursive pour arriver à faire cela. Cette fonction prend en paramètres la chaîne de caractères, et un tableau de booléens.

Le tableau de booléens fait la même taille que la chaîne. Chaque caractère de la chaîne est associé à une (et une seule case) du tableau de booléens. Le tableau de booléens permet au programme de bloquer telle ou telle lettre pour faire toutes les combinaisons possibles.

Voici, commenté, le corps de cette fonction. Une case du tableau assignée à false implique que la lettre correspondante n'est pas bloquée.

Code Java d'origine (= qui ne fonctionne pas)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Launcher {

    public static void main(String[] args) {
        String string = "abc"; // This string'll be used to display all the anagrams : "ABC" (this string) will give us : ABC - ACB - BAC - BCA - CAB - CBA for example

        boolean locked_characters[] = new boolean[string.length()]; // This array's size is equal to the string's one. Each case is associated with one (and only one) string's character. The array's values indicate if a character is or is not locked.
        for (int i = 0; i < locked_characters.length; i++) {
            locked_characters[i] = false;
        }

        displayAnagrams(string, locked_characters); // Original invocation (our algorithm is recursive)
    }


    private static void displayAnagrams(String string, boolean[] locked_characters) {
        for (int i = 0; i < string.length(); i++) {
            if (!locked_characters[i]) { // If the associated character must is not locked
                System.out.print(string.charAt(i));
                locked_characters[i] = true; // We won't display again this character : we lock it

                displayAnagrams(string, locked_characters); // Recursion
                System.out.print(" - ");
                locked_characters[i] = false; // We unlock this character (all "its" anagrams are displayed), we will lock the following one
            }
        }
    }

}

Code Java qui fonctionne

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Launcher {

    public static void main(String[] args) {
        String string = "ABCD"; // This string'll be used to display all the anagrams : "ABC" (this string) will give us : ABC - ACB - BAC - BCA - CAB - CBA for example

        boolean locked_characters[] = new boolean[string.length()]; // This array's size is equal to the string's one. Each case is associated with one (and only one) string's character. The array's values indicate if a character is locked or not.
        for (int i = 0; i < locked_characters.length; i++) {
            locked_characters[i] = false;
        }

        displayAnagrams(string, locked_characters, ""); // Original invocation (our algorithm is recursive)
    }


    private static void displayAnagrams(String string, boolean[] locked_characters, String displayed_anagram) {
        for (int i = 0; i < string.length(); i++) {
            if (!locked_characters[i]) {
                locked_characters[i] = true;

                displayAnagrams(string, locked_characters, displayed_anagram + string.charAt(i));

                locked_characters[i] = false;
            }
        }

        if(displayed_anagram.length() == string.length()) {
            System.out.println(displayed_anagram);
        }
    }

}

RÉSULTAT D’EXÉCUTION (du code qui ne marchait pas)

En entrée :

abc

En sortie :

abc - - cb - - - bac - - ca - - - cab - - ba - - -

RÉSULTAT D’EXÉCUTION du code qui marche

En entrée :

ABCD

En sortie (NB : les espaces qu'affiche ZdS sont en réalité des retour à la ligne) :

ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA

Explications sur le source

On lance pour la première fois la méthode displayAnagrams (en effet, notre algorithme est récursufi, cf. la suite de mon explication). Elle possède notamment le paramètre displayed_anagram, qui correspond à l'anagramme (qui est construit petit à petit). Ce paramètre est initialisé à : "" (chaîne vide). Voici ce que fait cette méthode.

Elle parcourt chaque caractère de la chaîne originelle. Si le caractère courant est marqué comme étant "bloqué", rien ne se passe.

Chacun d'eux est d'abord marqué comme étant "bloqué".

Dès qu'un caractère est marqué "bloqué", on fait un appel récursif à displayAnagrams. Dans cet appel récursif, le paramètre displayed_anagram est assigné à displayed_anagram + <caractere_marqué_bloqué>.

Dès qu'un niveau de récursivité est terminé, le niveau de récursivité appelant peut enfin reprendre. Il commencera par débloquer son caractère courant. Puis il continuera de parcourir la chaîne originelle.

Enfin, après le for, c'est-à-dire une fois la chaîne totalement parcourue, on affiche la valeur de displayed_anagram, qui contient l'anagramme ainsi formé.

QUESTIONS

  1. Le gros problème est que le blocage d'un caractère va empêcher son affichage plus d'une fois. EXEMPLE : pour l'anagramme dont la lettre bloquée est "A" on a : ABC et CB. Au lieu de ABC et ACB. Comment résoudre ce problème ? En transmettant par paramètre la lettre bloquée ? N'est-ce pas un peu tricher ?

  2. Comment enlever les " - " en trop ? :o

Je vais continuer de travailler sur le problème n°1 avant de passer au 2, mais si possible je voudrais bien un peu d'aide pour éclaircir tout ça.

PS : je n'ai pas de souci particulier avec la récursivité d'un point de vue technique. En revanche, j'avoue que son utilisation ici m'intrigue un peu dans le sens où je n'arrive pas à avoir une vision globale du fonctionnement de l'algorithme. Quand je le déroule à la main, je vois que j'obtiens bien des anagrammes mais j'ai du mal à le comprendre d'une manière intuitive.

Merci d'avance et bonne soirée !

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0
Staff

Salut,

J'ai du mal à comprendre ce que tu veux dire par "on bloque les lettres". Cette conception avec un tableau de boolééns me semble assez foireuse, c'est imposé ou c'est de ton cru ?

Il me semblerait beaucoup plus logique de dire que les anagrammes de ABC sont décrits de la manière suivante :

  • l'ensemble des anagrammes de BC avec A ajouté devant ;
  • l'ensemble des anagrammes de AC avec B ajouté devant ;
  • l'ensemble des anagrammes de AB avec C ajouté devant.

Je te laisse réfléchir à cette idée pour généraliser à n'importe quelle chaîne de longueur quelconque.

I don't mind that you think slowly, but I do mind that you are publishing faster. – W. Pauli

+0 -0
Auteur du sujet

En effet, cette façon de faire m'est imposée ! Pas de souci pour explorer ta méthode, mais ce sera plutôt dans un deuxième temps du coup ^^'

"On bloque les lettres", ça veut dire, si j'ai bien compris ce qu'a dit le prof, qu'on n'affiche les anagrammes selon l'ordre qu'elles définissent…

Université de Bretagne-Sud <3

+0 -0
Auteur du sujet

Oyez oyez ! :)

J'ai finalement réussi à écrire l'algorithme. Celui-ci ne me semble pas des plus faciles à comprendre, je vais faire de mon mieux pour l'expliquer. N'hésitez pas à faire des remarques.

J'ai mis à jour l'OP avec mon nouveau code, que vous trouverez ci-dessous également :) :

Code-source qui marche

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Launcher {

    public static void main(String[] args) {
        String string = "ABCD"; // This string'll be used to display all the anagrams : "ABC" (this string) will give us : ABC - ACB - BAC - BCA - CAB - CBA for example

        boolean locked_characters[] = new boolean[string.length()]; // This array's size is equal to the string's one. Each case is associated with one (and only one) string's character. The array's values indicate if a character is locked or not.
        for (int i = 0; i < locked_characters.length; i++) {
            locked_characters[i] = false;
        }

        displayAnagrams(string, locked_characters, ""); // Original invocation (our algorithm is recursive)
    }


    private static void displayAnagrams(String string, boolean[] locked_characters, String displayed_anagram) {
        for (int i = 0; i < string.length(); i++) {
            if (!locked_characters[i]) {
                locked_characters[i] = true;

                displayAnagrams(string, locked_characters, displayed_anagram + string.charAt(i));

                locked_characters[i] = false;
            }
        }

        if(displayed_anagram.length() == string.length()) {
            System.out.println(displayed_anagram);
        }
    }

}

Explications sur le source

On lance pour la première fois la méthode displayAnagrams (en effet, notre algorithme est récursufi, cf. la suite de mon explication). Elle possède notamment le paramètre displayed_anagram, qui correspond à l'anagramme (qui est construit petit à petit). Ce paramètre est initialisé à : "" (chaîne vide). Voici ce que fait cette méthode.

Elle parcourt chaque caractère de la chaîne originelle. Si le caractère courant est marqué comme étant "bloqué", rien ne se passe.

Chacun d'eux est d'abord marqué comme étant "bloqué".

Dès qu'un caractère est marqué "bloqué", on fait un appel récursif à displayAnagrams. Dans cet appel récursif, le paramètre displayed_anagram est assigné à displayed_anagram + <caractere_marqué_bloqué>.

Dès qu'un niveau de récursivité est terminé, le niveau de récursivité appelant peut enfin reprendre. Il commencera par débloquer son caractère courant. Puis il continuera de parcourir la chaîne originelle.

Enfin, après le for, c'est-à-dire une fois la chaîne totalement parcourue, on affiche la valeur de displayed_anagram, qui contient l'anagramme ainsi formé.

Édité par The-Aloha-Protocol

Université de Bretagne-Sud <3

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte