Algorithme de combinaisons

Version imprimable

01/05/2011, 02h06
kerimos

Algorithme de combinaisons

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 !
01/05/2011, 08h07
DOLPat®

Bonjour

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

Pat.
01/05/2011, 21h55
kerimos

Merci

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.
02/05/2011, 06h59
DOLPat®

Bonjour

Citation:

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

Tu auras du mal à faire plus rapide ...sous Pascal. Va falloir faire un morceau de code en assembleur si tu veux de la rapidité...
02/05/2011, 07h16
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 :)
02/05/2011, 10h09
GoustiFruit

Citation:

Envoyé par DOLPat®

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.
02/05/2011, 11h13
ShaiLeTroll

Citation:

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

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 !

Citation:

Envoyé par ShaiLeTroll

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 .

Citation:

Envoyé par ShaiLeTroll

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:

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:

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)); } }
Citation:

Envoyé par ShaiLeTroll

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.

Citation:

Envoyé par ShaiLeTroll

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 ?

02/05/2011, 17h44
DOLPat®

Bonjour

Citation:

Envoyé par GoustiFruit

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...
02/05/2011, 18h11
Paul TOTH

Citation:

Envoyé par DOLPat®

Bonjour

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

as-tu déjà comparer les performances du même code compilé avec Delphi et avec FPC ? je ne sais pas ce que ça donne.
02/05/2011, 18h50
DOLPat®

Bonjour

Citation:

Envoyé par Paul TOTH

as-tu déjà comparer les performances du même code compilé avec Delphi et avec FPC ? je ne sais pas ce que ça donne.

Non, mais je viens de me prêter au jeu.
Delphi 2005 32 bits: 5,8s
FPC 2.4.3 64 bits: 6,5 s
Donc pour ce morceau de code (travail sur caractères et stockage du résultat dans un TMemo) Delphi 2005 vieillissant gagne haut la main.

[Edit]
J'ai commis une petite erreur lors de mes tests. En effet, les relevés précédents ont été faits en exécutant l'application dans les EDI respectifs, donc avec le déboggeur actif.
J'ai donc effectué les mêmes essais en lançant l'application directement et voici ce que cela donne:
Delphi 2005 32 bits: 4,35s
FPC 2.4.3 64 bits: 4,4 s

Au vu de ces nouveau essais, j'en tire la conclusion suivante: Match nul, balle au centre.
02/05/2011, 21h01
GoustiFruit

L'idéal ça serait de pouvoir utiliser la puissance des GPU avec Delphi :-) J'ai longtemps attendu un portage de CUDA mais il n'est jamais venu :cry:
03/05/2011, 16h08
ShaiLeTroll

Citation:

Envoyé par kerimos

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 !

Citation:

Envoyé par ShaiLeTroll

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

Citation:

Envoyé par kerimos

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.

Citation:

Envoyé par kerimos

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 !

Citation:

Envoyé par kerimos

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)

Citation:

Envoyé par kerimos

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:mouarf:) 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" !
03/05/2011, 21h06
Caribensila

Salut,

Citation:

...mais on vas facher Caribensila qui ne semble pas aimer le recursif (pourtant c'est utile voir indispensable pour certains algo utilisant des arbres)

Ce n'est pas que ça me fâche, Shai. Et c'est même certainement très utile dans certains cas comme tu le dis.
J'irai même jusqu'à dire que c'est une démarche intellectuelle qui me séduit beaucoup, d'autant qu'elle ne vient pas naturellement pour la plupart d'entre nous et que le premier jet est souvent itératif chez les occidentaux.
Mais j'ai rencontré de trop nombreux programmeurs qui pensaient optimiser leur algo en le récursifiant en ignorant qu'en fait ils le plombaient (voir tous les exemples du QuickSort qu'on trouve sur le Net en récursif !).

Bref, pour moi, récursifier un algo pour l'optimiser est une idée reçue qu'il convient de combattre afin que chacun sache ce qu'il fait et où il va.

Ceci dit, je changerai d'avis le jour où on me montrera un algo récursif plus performant que le même en itératif.
Et dans les cas où la vitesse d'exécution n'est pas compromise, le récursif est plus concis et donc conseillé.
04/05/2011, 00h10
Caribensila

Petite minute culturelle :

Il faut toujours se méfier quand on parle "milliard" avec des étrangers. :)

Aux USA, dans le langage courant, 1 milliard (français) se dit 1 billion; et 1 milliard (US) c'est 1 000 billions (US).
Mais, en France, 1 millard c'est 1 000 millions; et 1 billion c'est 1 million de millions.
Ainsi, il est plus rapide de devenir $-milliardaire en France qu'aux USA, bien que ce ne soit pas plus facile qu'en Angleterre.

Bref, si vous n'avez pas tout suivi, c'est ici ... et préférez parler en puissance de dix (sauf avec les femmes qui préfèrent les milliards... de n'importe quoi). ;)

En Tunisie, on peut penser que c'est le même milliard, celui du français !

Effectivement calculer 10^9 mots (milliard de mots) de 5 lettres sur un alphabet de 67 lettres, on arrive à un temps théorique avec les meilleurs algo du sujet de 16 minutes pour 6Go de Données, cela reste envisageable mais si l'on prend en considération que l'on souhaite calculer 10^12 mots (billion de mots) de 7 lettres sur un alphabet de 67 lettres (qui en compte en réalité 400x10^12), on arrive effectivement à plus de 11 jours mais surtout à 8 To de Données, franchement personne n'aurait une telle idée (sauf les logiciels de crack)

Donc désolé, si il y a eu méprise sur le terme milliard, après tout c'est un forum francophone, on s'attend à l'utilisation des bons termes !

Maintenant, comme on l'a déjà dit, trouver les arrangements avec répétition, c'est un simple Algo de conversion de base au lieu d'utiliser 0..9 ou 0..9ABCDEF on utilise a..zA..Z0..9... (avec une table de conversion, on peut utilisé n'importe quel alphabet)

Petite illustration que la Conversion de Base fonctionne aussi bien pour convertir en octal ou hexadécimal, ou calculer des arrangements avec répétitions
GetArrangementAvecRepetition permet de récupérer le ieme arrangement avec répétition sur n'importe quel alphabet de n objets et n'importe quel taille de mot de k emplacements tant que n^k ne dépasse pas 2^63 ~= 9x10^18
Code:

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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 //--------------------------------------------------------------------------- AnsiString __fastcall ConversionIntToBase(__int64 Value, const AnsiString &Base) { AnsiString Result = ""; int BaseLen = Base.Length(); if (BaseLen >= 0) { if (Value >= BaseLen) { Result.SetLength(Floor(LogN(BaseLen, Value)) + 1); // LogN est-il plus rapide que des réallocations de chaine dans une boucle ? char* pResult = Result.AnsiLastChar(); while (Value > 0) { *pResult = Base[Value % BaseLen + 1]; Value = Value / BaseLen; // Division entière en C++ grace au type ! pResult--; } } else Result = Base[Value + 1]; } return Result; } //--------------------------------------------------------------------------- AnsiString __fastcall GetArrangementAvecRepetition(const AnsiString &Objets, int LongueurArrangement, __int64 Index) { AnsiString Result; Result.SetLength(LongueurArrangement); int TabSize = Objets.Length(); for (int J = LongueurArrangement; J > 0 ; J--) { Result[J] = Objets[Index % TabSize + 1]; Index = Index / TabSize; // Division entière en C++ grace au type ! } return Result; } //--------------------------------------------------------------------------- void __fastcall TMathForm::BtnConvertionBaseClick(TObject *Sender) { MemoTrace->Lines->Add("---"); AnsiString Objets = "01234567"; for (int i = 0; i <= 257; i++) MemoTrace->Lines->Add(IntToStr(i) + " : " + ConversionIntToBase(i, Objets)); MemoTrace->Lines->Add("---"); Objets = "0123456789ABCDEF"; for (int i = 0; i <= 257; i++) MemoTrace->Lines->Add(IntToStr(i) + " : " + ConversionIntToBase(i, Objets)); MemoTrace->Lines->Add("---"); Objets = "azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN0123456789_$&#@"; for (int i = 0; i <= 67; i++) { MemoTrace->Lines->BeginUpdate(); for (int ii = 0; ii < 67; ii++) { MemoTrace->Lines->Add(IntToStr(i * 67 + ii) + "\t : " + ConversionIntToBase(i * 67 + ii, Objets) + " - \t" + GetArrangementAvecRepetition(Objets, 1, i * 67 + ii) + " - \t" + GetArrangementAvecRepetition(Objets, 2, i * 67 + ii) + " - \t" + GetArrangementAvecRepetition(Objets, 3, i * 67 + ii)); } MemoTrace->Lines->EndUpdate(); } MemoTrace->Lines->Add(IntToStr(123456789) + "\t : " + ConversionIntToBase(123456789, Objets) + " - \t" + GetArrangementAvecRepetition(Objets, 5, 123456789)); MemoTrace->Lines->Add(IntToStr(123456789123456789i64) + "\t : " + ConversionIntToBase(123456789123456789i64, Objets) + " - \t" + GetArrangementAvecRepetition(Objets, 10, 123456789123456789i64)); } //---------------------------------------------------------------------------

04/05/2011, 20h10
kerimos

Citation:

Envoyé par ShaiLeTroll

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)

Ma mère est prof de maths , j'ai eu mon bac section maths avec 18,66 , j'ai fait 2 ans de préparatoire section Maths Physique Informatique , maintenant je donne des cours en maths aux bacheliers et j'étudie encore du maths dans mes études d’ingénieurs !!!!!!!
Moi je voulais dire un million de million et non un milliards ça arrive des erreurs comme ça je me suis concentré au résultat qui est un million et j'ai du me tromper du nom du nombre du combinaisons qui est en faite mille milliards et non un milliard.
Monsieur "ShaiLeTroll" , si je dis " tu a tombé dans l'escalier " ça ne veut pas dire que je suis nul en français , peut être que j'ai pensé à dire tu as chuté et finalement j'ai écrit tu as tombé au lieu de tu es tombé.
Je vous ai dis que c'est bon pour l'algorithme je n'ai pas lu ton dernier algorithme car vraiment j'ai beaucoup d'autres projets. ( c'étais pour un brute force la recherche des combinaisons :mouarf:)
Pour le cloud , je crois que je développer une petite application web sur google app engine avec java MVC.
La tunisie vous passe le salut :)