Discussion :

[kerimos]

Bonjour tout le monde , j'essaye de trouver un algorithme qui effectue la combinaison avec répétition de toutes les possibilités à partir des éléments d'un tableau et d'une longueur n .
c'est à dire si le tableau = { A,B,C} et n=2 le résultat sera:
AA
BB
CC
AB
BA
AC
CA
BC
CB

( si n=3 on aura AAB AAC etc ... )
c'est un vrai 'casse tête' je le sais.
Merci d'avance !

[DOLPat®]

Bonjour

le sujet a déjà été abordé dans cette discussion. Tu y trouvera aussi un code exemple.

Pat.

[kerimos]

En faite il me faut cet algorithme pour un brute force , malheureusement l'algorithme que j'ai trouvé ici est tellement de complexité trop élevé qu'il me faut quelques semaines d'exécutions pour obtenir le résultat .
En plus il m'a fallut diminuer le taille des possibilités à 7 pour ne pas avoir une erreur d'abus de mémoire.

[DOLPat®]

Bonjour

En faite il me faut cet algorithme pour un brute force , malheureusement l'algorithme que j'ai trouvé ici est tellement de complexité trop élevé qu'il me faut quelques semaines d'exécutions pour obtenir le résultat .

Tu auras du mal à faire plus rapide ...sous Pascal. Va falloir faire un morceau de code en assembleur si tu veux de la rapidité...

[Paul TOTH]

c'est toujours le même principe, soit le code est hyper rapide, soit on sort du traitement tout ce qu'on peut.

ici pas la peine d'optimiser les choses, en stockant toutes les combinaisons dans un fichier, quitte a passer 3 jours à générer le fichier, tu n'as ensuite plus qu'à lire le fichier, et ça c'est rapide...il faut juste de la place disque

[GoustiFruit]

Bonjour



Tu auras du mal à faire plus rapide ...sous Pascal. Va falloir faire un morceau de code en assembleur si tu veux de la rapidité...

Ne fais pas mon plus passer le Pascal pour moins efficace qu'il n'est: même en passant en assembleur, le gain ne sera pas "d'une autre échelle de grandeur"... Généralement Delphi/Pascal s'en sort très bien dans les benchmarks.

[DOLPat®]

Bonjour

Ne fais pas mon plus passer le Pascal pour moins efficace qu'il n'est: même en passant en assembleur, le gain ne sera pas "d'une autre échelle de grandeur"... Généralement Delphi/Pascal s'en sort très bien dans les benchmarks.

Ne me fais pas dire ce que je n'ai pas dis ! Néanmoins, dans certains cas, on peut diviser par 10 le temps d'exécution, voir plus, ce qui n'est pas négligeable. J'ai fait une application qui m'oblige à traiter des images en temps réel et il n'y a pas 'photo' entre mon code Pascal d'origine et la procédure Asm actuelle. Conclusion le Pascal est largement suffisant dans 99% des cas, mais pour le dernier %, l'usage de l'assembleur est utile. Et pourquoi s'en priverait-on puisque Delphi (et Lazarus qui est mon EDI) l'autorise...

[ShaiLeTroll]

En faite il me faut cet algorithme pour un brute force , malheureusement l'algorithme que j'ai trouvé ici est tellement de complexité trop élevé qu'il me faut quelques semaines d'exécutions pour obtenir le résultat .
En plus il m'a fallut diminuer le taille des possibilités à 7 pour ne pas avoir une erreur d'abus de mémoire.

Si tu as des erreurs de mémoire, c'est que tu n'as pas utilisé le bon algo, tu n'as pas vu à la fin du sujet indiqué par DOLPat® qu'il y avait un lien vers un autre sujet qui fourni des solutions avec utilisation d'un fichier et donc élimine le problème de mémoire
Pour le temps, on avait atteint moins d'une seconde pour générer un million d combinaison avec des machines de 2007 !
Encore une fois, je ne vois pas quel algo tu as pu choisir pour annoncer de tel temps !

Mais surtout une solution qui utilise un algorithme de conversion numérique proposé par E-ric !

Et où vois-tu un casse-tête ?

Pour l'assembleur, sur Phidels, j'ai souvent pondu des codes Pascal plus performant que certaines solutions assembleurs !
Ce qui compte en premier c'est l'algo, un mauvais algo ASM restera un mauvais Algo tout court !

[kerimos]

Si tu as des erreurs de mémoire, c'est que tu n'as pas utilisé le bon algo

Je n'ai pas utilisé le bon algorithme oui je sais , c'est pour quoi je demande l'avis des professionnels comme vous
Quand j'ai dit des erreurs d’espace de mémoire heep ce n'étais pas ça mon problème mais plutôt le temps d'exécution et le nombre des possibilités les deux élevés . car à part les fichiers je peux toujours "diviser" l'algorithme pour qu'à chaque exécution je teste un nombre exacte de possibilités .

tu n'as pas vu à la fin du sujet indiqué par DOLPat® qu'il y avait un lien vers un autre sujet qui fourni des solutions avec utilisation d'un fichier et donc élimine le problème de mémoire

Si si j'ai vu et d'ailleurs hier j'ai implémenté ceci https://www.developpez.net/forums/showthread.php?p=2069041 en Java:

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
 public static ArrayList<String> possiblite (int NbreCaractere , String caracteres )
	{
		int i ;
		//String [] AncList, NouvList;
		ArrayList<String> NouvList= new ArrayList<String>();
		ArrayList<String> AncList= new ArrayList<String>();
		char Elt ;
		String Chaine ;
 
 
		for (int j=0 ; j<caracteres.length() ; j++)
		{
			NouvList.add(caracteres.substring(j, j++));
		}
		for (i=2 ; i< NbreCaractere ; i++)
		{
			 effacer(AncList);
		     copier(AncList , NouvList);
		     for (int k= 0 ; k< AncList.size();k++)
		     {
		    	 for (int l=0 ; l<caracteres.length();l++)
		    	 {
		    		 NouvList.add(AncList.get(k)+caracteres.substring(l,l+1));
		    	 }
		     }
		}
return NouvList;

le main :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
public static void main ( String args[])
	{
 
	      String chaine = "azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789_$&#@";
	      int k= possiblite(4,chaine).size();
	      for (int i=0 ; i< k ;i++)
	      {
	    	  verifier(possiblite(4,chaine).get(i));
	      }
 
	}

Pour le temps, on avait atteint moins d'une seconde pour générer un million d combinaison avec des machines de 2007 !

Et s'il s'agit d'un milliards de combinaisons , il en faut moins d'un million de seconde ce qui fait plus que 11 jours , en plus vous l'avez remarquez je suppose qu'il y a une méthode vérification qui consomme le plus de temps.

Et où vois-tu un casse-tête ?

Tout est relatif monsieur , pour moi c'est un vrai casse tête

Pour terminer j'ai vu que tout le monde parle de l'assembleur , je n'ai jamais codé en assembleur moi et je ne compte pas me pencher vers un si vaste langage pour le moment .

En conclusion merci à tous , c'est bon mon collègue a pu trouver le résultat avec un algorithme récursif.

A part ça est ce que quelqu’un pourrait me confier une idée d'un mini projet (petite application) sur le cloud computing ?

[ShaiLeTroll]

Je n'ai pas utilisé le bon algorithme oui je sais , c'est pour quoi je demande l'avis des professionnels comme vous

je parlais des algos du sujet pas du tien !
en plus, les pros ne font que très rarement ce genre de développement, quel est l'intéret de calculer des combinatoires alors de 90% des logiciels Delphi concerne la paye, la compta, la RH, la finance et un peu de Multimedia comme Skype ou chez Archos

Ta programme Java pour cet alphabet pour des mots de 4 lettres, tu proposeras 20 151 121 de combinaisons, donc environ 70 Mo de texte pure, une TStringList en Delphi, cela représenterait 210Mo en D7 et 500Mo en DXE

Cela reste gérable !

Pour le temps, on avait atteint moins d'une seconde pour générer un million d combinaison avec des machines de 2007 !

Et s'il s'agit d'un milliards de combinaisons , il en faut moins d'un million de seconde ce qui fait plus que 11 jours , en plus vous l'avez remarquez je suppose qu'il y a une méthode vérification qui consomme le plus de temps.

Tout est relatif monsieur , pour moi c'est un vrai casse tête

Ouch !
Si 1 millions de combinaisons peuvent être calculé en 1 seconde
Tu me réponds que pour 1 milliards de combinaions, il faut 1 million de seconde !
je comprends que pour toi c'est un casse tête, tu es nul en math (la combinatoire, c'est des math, tu ne maitrise pas la règle de 3 utilisant des divisions)

Règle de 3
1s = 1000000c
???? s = 1000000000c

La réponse est 1000 ! pas un million !
ça ne fait que 16 minutes, bon un milliard de combinaison, avec ton alphabet a..zA..Z0..9_$&#@, cela fait des mots de 5 lettres, donc au moins 6Go de fichier !

Pour terminer j'ai vu que tout le monde parle de l'assembleur , je n'ai jamais codé en assembleur moi et je ne compte pas me pencher vers un si vaste langage pour le moment .

Euh, c'est l'inverse, l'ASM est un langage plus réduit que Delphi, il y nettement plus d'instruction (procédural ou POO) en Delphi qu'il y a de codop en ASM (surtout si tu te limite au X86 de base, si tu rajoutes le MMX et les SSE, c'est comme si tu ajoutais Jedi et GLScene à Delphi)
Mais, tu as raison, d'abord apprendre à coder avec des langages "classiques" comme le C ou pascal, puis une fois maitrisé s'attaquer à l'ASM (surtout que celui intégré à Delphi est assez particulier)

En conclusion merci à tous , c'est bon mon collègue a pu trouver le résultat avec un algorithme récursif.

Ce n'est pas surprenant, dans le sujet "Test possibilités possible longue boucle", les premiers algos étaient récursifs
mais on vas facher Caribensila qui ne semble pas aimer le recursif (pourtant c'est utile voir indispensable pour certains algo utilisant des arbres)

HS
Pour le cloud computing : c'est plus une architecture qu'une problématique logicielle.
Pour moi c'est avant tout un concept, pas éloigné de la délocalisation des usines, on fait fabriquer ailleurs pas cher pour le vendre tout aussi cher ici !
On va te louer un serveur virtuel au pris du serveur physique si tu l'avais acheté. tout est une histoire amortissement\investissement comme le leasing !

Imaginons un programme qui calcule en permanence des combinatoires (tu veux craquer le compte bancaire de madoff) et offre un service pour obtenir les combinaisons déjà calculées.
Si tu l'installes sur un serveur virtuel (on en trouve des gratuits même chez MS), tu déportes son execution, c'est déjà du cloud computing ...

Le Projet SETI ne peut-il pas être considéré comme du cloud computing avant l'heure (quasiment 10 ans), les auteurs du programme ont utilisé comme support de calcul tous les ordinateurs "offerts" par les internautes, ils ont formé un réseau (un nuage) d'ordinateurs, on avait une sorte de "cloud public gratuit" !