Discussion :

[zeusolym]

Bonjour à tous,
Actuellement j'aurai besoin pour une épreuve de connaître toutes les combinaisons de 8 caractères que l'on peut obtenir à partir de la chaîne "azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789_$&#@" ...

J'ai entendu parler de "l'étoile de Kleene" qui, après de petites recherches, semble correspondre, mais je ne sais malheureusement pas comment la mettre en oeuvre en Java

J'aimerai savoir si certains ont déjà rencontré cette nécessité ou sauraient comment résoudre ce problème (ou, si une discussion qui en parle m'a échappé, avoir un lien y menant).

J'ai tenté ceci de mon côté, mais si quelqu'un a un code plus efficace ... :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
import java.io.* ;
public class js
{
    static String tab="azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789_$&#@";
    static int taille=tab.length();
 
    public static void main(String[] args)throws IOException{
        generer(8, "");
    }
 
// nbr : nombre de caractères que doivent contenir les chaînes de résultat
public static void generer(int nbr, String sb) throws IOException
   {String result = "";
    if (sb.length()==nbr)
    {
         //on enregistre la chaîne
         result += sb + "\n";
         return;
    }
   //taille est la longeur totale de la chaîne de référence
    for(int i=0; i<taille; i++)
    {
      generer(nbr, sb+tab.charAt(i));
    }
 
    //Ici FluxFichier.écrire() est une méthode perso qui écrit dans
//un fichier passé en argument le contenu d'un chaîne passée en argument2
	FluxFichier.écrire("/home/lev-arcady/Documents/test.txt", result);
   }
}

Merci de votre aide !

[Uther]

Laisse juste tomber, tu vas droit dans le mur. Tu vas exploser les limites de mémoire/fichier très rapidement.
Pour ton exemple avec les combinaisons 8 caractères parmi 67, il y a 67^8 résultats qui occuperont au minimum 8 octets soit un total d'environ 2 954 To (3 025 439 Go)

[zeusolym]

Aïe :p me disais aussi qu'un calcul qui n'a toujours pas fini en une nuit non-stop ...

Edit : je viens de m'apercevoir en relisant l'épreuve qu'il s'agit non pas de 8 mais de 6 caractères ... donc 67^6 solutions selon toute logique (ce qui m'avance un peu mais pas trop).

Et si j'ajoute une condition comme ne pas prendre en compte le résultat s'il contient 3x ou plus le même caractère de suite, histoire de garder les solutions ayant possiblement un sens, tu penses que ça réduirait ce chiffre de beaucoup ou pas ?

Edit 2 : voilà le code que j'ai incluant cette condition :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
32
33
34
35
36
37
38
39
40
import java.io.* ;
public class js
{
    static String tab="azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789_$&#@";
    static int taille=tab.length();
 
    public static void main(String[] args)throws IOException{
        generer(6, "");
    }
 
// nbr : nombre de caractères que doivent contenir les chaînes de résultat
public static void generer(int nbr, String sb) throws IOException
   {
	breaker : {String result = "";
    if (sb.length()==nbr)
    {
    	char [] prob = sb.toCharArray();
    	for(int h=0; h<3; h++){
    		if(prob[h]==prob[h+1] && prob[h+1]==prob[h+2]){
    			//Si trois caractères de suite sont identiques, on passe à la combinaison suivante;
    			//sinon on décale le test d'un caractère et ce jusqu'à avoir testé toute la combinaison
    			break breaker;
    		}
    	}
         //on enregistre la chaîne
         result += sb + "\n";
         System.out.println(sb);
         return;
     }
   //taille est la longeur totale de la chaîne de référence
    for(int i=0; i<taille; i++)
    {
      generer(nbr, sb+tab.charAt(i));
    }
 
    //Ici FluxFichier.écrire() est une méthode perso qui écrit dans un fichier passé en argument le contenu d'un chaîne passée en argument2
	FluxFichier.écrire("/home/lev-arcady/Documents/test.txt", result);
   }
   }
}

[Uther]

Je viens de m'apercevoir en relisant l'épreuve qu'il s'agit non pas de 8 mais de 6 caractères ... donc 67^6 solutions selon toute logique (ce qui m'avance un peu mais pas trop).

Et si j'ajoute une condition comme ne pas prendre en compte le résultat s'il contient 3x ou plus le même caractère de suite, histoire de garder les solutions ayant possiblement un sens, tu penses que ça réduirait ce chiffre de beaucoup ou pas ?

Ça reste un résultat qui prendrait plusieurs centaines de Go à stocker, je suppose qu'il y a une incompréhension sur l’énoncé de ton exercice. J'imagine mal un professeur donner un exercice qui met a genoux une machine standard.

Je suppose que ce que ton professeur attend c'est les combinaisons au sens mathématique ce qui donnerais 67!/(6!*61!) résultats soit environ 100 millions. On aurait une quantité de résultat gérable.

Un autre éventuel problème serait ta méthode

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

FluxFichier.écrire("/home/lev-arcady/Documents/test.txt", result)

qui, je suppose va ré-ouvrir le fichier à chaque écriture ce qui risque de fortement ralentir, à moins qu'elle garde dans une sorte de cache les connexions aux fichier passés en paramètre en cache.

[zeusolym]

Je suppose que ce que ton professeur attend c'est les combinaisons au sens mathématique ce qui donnerais 67!/(6!*61!) résultats soit environ 100 millions. On aurait une quantité de résultat gérable.

Très bien je fonce sur le lien Merci

Un autre éventuel problème serait ta méthode

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

FluxFichier.écrire("/home/lev-arcady/Documents/test.txt", result)

qui, je suppose va ré-ouvrir le fichier à chaque écriture ce qui risque de fortement ralentir, à moins qu'elle garde dans une sorte de cache les connexions aux fichier passés en paramètre en cache.

Il me semble, mais peut-être est-ce une erreur de ma part, que cette méthode est placée de façon à écrire, une fois les combinaisons générées, l'ensemble, non ? Sinon effectivement le fichier est ouvert puis fermé après l'écriture par cette méthode, que voici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void écrire(String place, String texte) throws IOException{
		annuler : 
		{try
		{
			private static PrintWriter scribe = new PrintWriter(new FileWriter(place));
			scribe.println(texte);
		}
 
		catch(IOException e){
			System.out.println("Une exception de type IOException est survenue. L'action est annulée");
			break annuler;
		}
		}
	scribe.close();
	}

[Uther]

En effet, j'avais regardé le code un peu vite.

Il faudrait que tu ouvres le flux au début et que tu écrive dedans au fur et a mesure, sinon tu satureras la mémoire.