Mélangeur de caractères

[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)

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

Merci d'avance et bonne soirée !

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.

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…

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é.