|
pb algorithme de combinaison |
Débuté par azert, 09 sep. 2010 15:46 - 21 réponses |
| |
| | | |
|
| |
Posté le 09 septembre 2010 - 15:46 |
bonjour
j'ai un souci d'algo j'ai une chaine de x lettres (ex : ABCDEF) je veux pouvoir:
afficher toutes les combinaisons possibles de ces x-1 lettre
dans mon exemple de 6 lettres (ABCDEF) je pourrais avoir : ABCDE ABCDF DACEF ...
en fait ca ressemblerait au scrabble quoi (sauf que dans mon cas, je ne traite pas des vrais mots)! |
| |
| |
| | | |
|
| | |
| |
Posté le 09 septembre 2010 - 17:48 |
Bonjour,
Je viens de faire ce bout de code qui devrais faire l'affaire il est fait vite fait donc pas trop de commentaire desolé, si vous ne comprenez pas prévenez moi
sMaChaine est une chaîne = "ABCEF" sChaineNew est une chaîne nNbPossibilite est un entier nLong est un entier = Taille(sMaChaine)
ptabCaractUnik est un tableau dynamique ptabPosition est un tableau dynamique
ptabCaractUnik = allouer un tableau dynamique de nLong chaînes ptabPosition = allouer un tableau dynamique de nLong entier
POUR I = 1 A nLong ptabCaractUnik[I] = Milieu(sMaChaine,I,1) FIN
POUR I = 1 A nLong ptabPosition[I] = 0 FIN
nFinBoucle est un entier = 1 nSommePosition est un entier = 1 POUR I = 1 A nLong nSommePosition = nSommePosition * I nFinBoucle = nFinBoucle * nLong FIN
nPosIncrement est un entier nNvaleur est un entier sChainePos est une chaîne
BOUCLE nPosIncrement = nLong POUR I = 1 A nLong SI I = nPosIncrement ALORS ptabPosition[I] = ptabPosition[I]+1 SI ptabPosition[I] > nLong ALORS ptabPosition[I]= 1 POUR J = nLong-1 A 1 PAS -1 ptabPosition[J] = ptabPosition[J] + 1 SI ptabPosition[J] > nLong ALORS ptabPosition[J] = 1 SINON SORTIR FIN FIN FIN FIN nNvaleur = 1 sChainePos = "" POUR J = 1 A nLong nNvaleur = nNvaleur*ptabPosition[J] sChainePos = sChainePos+ptabPosition[J] FIN SI nNvaleur = nFinBoucle ALORS
SORTIR FIN sChaineNew = "" SI nNvaleur = nSommePosition ALORS
POUR I = 1 A nLong sChaineNew = sChaineNew+ptabCaractUnik[ptabPosition[I]] FIN Trace(sChaineNew) nNbPossibilite++ FIN FIN Libérer ptabCaractUnik Libérer ptabPosition Info("il y a "+nNbPossibilite+" possibillités")
BON DEV |
| |
| |
| | | |
|
| | |
| |
Posté le 09 septembre 2010 - 18:14 |
Correction, il y avais des erreurs a la suppression des doublons DSL
sMaChaine est une chaîne ="ABCEF" sChaineNew est une chaîne nNbPossibilite est un entier nLong est un entier = Taille(sMaChaine)
ptabCaractUnik est un tableau dynamique ptabPosition est un tableau dynamique
ptabCaractUnik = allouer un tableau dynamique de nLong chaînes ptabPosition = allouer un tableau dynamique de nLong entier
POUR I = 1 A nLong ptabCaractUnik[I] = Milieu(sMaChaine,I,1) FIN POUR I = 1 A nLong ptabPosition[I] = 0 FIN nFinBoucle est un entier = 1 bValeurCorrecte est un booléen POUR I = 1 A nLong nFinBoucle = nFinBoucle * nLong FIN
nPosIncrement est un entier nNvaleur est un entier sChainePos est une chaîne
BOUCLE nPosIncrement = nLong POUR I = 1 A nLong SI I = nPosIncrement ALORS ptabPosition[I] = ptabPosition[I]+1 SI ptabPosition[I] > nLong ALORS ptabPosition[I]= 1 POUR J = nLong-1 A 1 PAS -1 ptabPosition[J] = ptabPosition[J] + 1 SI ptabPosition[J] > nLong ALORS ptabPosition[J] = 1 SINON SORTIR FIN FIN FIN FIN nNvaleur = 1 sChainePos = "" bValeurCorrecte = Vrai POUR J = 1 A nLong nNvaleur = nNvaleur*ptabPosition[J] sChainePos = sChainePos+ptabPosition[J] FIN POUR I = 1 A nLong SI ChaîneOccurrence(sChainePos,NumériqueVersChaîne(I)) > 1 OU ChaîneOccurrence(sChainePos,"0") > 0 ALORS bValeurCorrecte = Faux FIN FIN SI nNvaleur = nFinBoucle ALORS SORTIR FIN sChaineNew = "" SI bValeurCorrecte ALORS POUR I = 1 A nLong sChaineNew = sChaineNew+ptabCaractUnik[ptabPosition[I]] FIN Trace(sChaineNew) nNbPossibilite++ FIN FIN Info("il y a "+nNbPossibilite+" possibillités") . |
| |
| |
| | | |
|
| | |
| |
Posté le 09 septembre 2010 - 19:52 |
bonjour, il y a un mois , j'avais écris un code qui ressemble à ce que tu recherches : En m'inspirant d'un code écrit en delphi ( merci à ludodelphi) j'ai réussi à bricoler un code qui a l'air de marcher. Algo avec récursivité qui donne les combinaisons possibles de k éléments parmi pop. J'utilise un tableau pour énumérer les éléments possibles mais les calculs se font sur des octets donc c'est limité à 256 éléments MAX. A vous de voir les limites,les bugs, les plantages, et les optimisations possibles :
ListeCombine est un tableau dynamique MaxCbn,cptCbn sont des entiers sur 8 octets k,Pop sont des octets
MonTableau est un tableau de chaînes i,j sont des entiers Combi est une chaîne
TableauAjoute(MonTableau,"A") TableauAjoute(MonTableau,"B") TableauAjoute(MonTableau,"C") TableauAjoute(MonTableau,"D") TableauAjoute(MonTableau,"E") TableauAjoute(MonTableau,"F")
k = 3 Pop = TableauOccurrence(MonTableau) MaxCbn = cnp(k,Pop) ListeCombine = allouer un tableau de MaxCbn + 1 par Pop octets cptCbn=0
CalculCombine(0) POUR i = 1 A MaxCbn Combi = "" POUR j=1 A k Combi = Combi + " " + MonTableau[ListeCombine[i,j]] FIN Trace(Combi)
FIN Libérer ListeCombine
Procedure cnp(c,p) i est un entier resultat est un entier = 1 POUR i = p-c+1 A p resultat = (resultat*i) /(i-(p-c)) FIN RENVOYER resultat
Procedure CalculCombine(niv est un entier) i,j,deb sont des octets
SI niv=0 ALORS deb = 1 SINON deb =ListeCombine[cptCbn+1,niv]+1 FIN POUR i = deb A Pop-(k-1)+niv ListeCombine[cptCbn+1,niv+1] = i SI niv = k-1 ALORS cptCbn++ POUR j = 1 A Pop ListeCombine[cptCbn+1,j]= ListeCombine[cptCbn,j] FIN SINON CalculCombine(niv+1) FIN FIN
Un peu hard je l'avoue
Ami calmant, J.P |
| |
| |
| | | |
|
| | |
| |
Posté le 09 septembre 2010 - 19:54 |
Bonjour, Attention aux combinaisons doubles qui ne sont pas exclues si au moins 2 lettres sont identiques. Exemple pour la chaine "AA" l'algo donné fournit 2 combinaisons ! A voir si cela est important ou pas ....
Michel. |
| |
| |
| | | |
|
| | |
| |
Posté le 09 septembre 2010 - 23:46 |
En effet, C'est pour cela que j'ai corrigé, mon code ( 2 emme poste) qui supprime les doublons J'avoue que le code est un peu hard , mais il a l'air de fonctionner , j'ai essayé avec 6 lettres |
| |
| |
| | | |
|
| | |
| |
Posté le 10 septembre 2010 - 08:48 |
bonjour, Désolé mais le code que j'ai posté plus haut ne tient pas compte des permutations.
petit rappel d'analyse combinatoire : COMBINATOIRE DE P OBJETS PARMI N Exemple p = 5 et n = 6 PERMUTATIONS ordre P = p! 120 ARRANGEMENTS ordre A = n! / (n-p)! 720 COMBINAISONS sans ordre C = A/P = n!/(n-p)!p! 6
Exemples divers : Combinaisons de 3 chevaux parmi 10 Tiercé dans le désordre C3 10 =10!/(3!(10-3)!) = 10!/(3! x 7!)=120
Au poker C5 52 = 2 598 960 Au loto C6 49 = 13 983 816 Arrangement de 3 chevaux parmi 8 Tiercé dans l'ordre A3 8 = 8!/(8-3)! = 8!/5!= 336 Apparemment tu recherches les arrangements plutôt que les combinaisons. il faut écrire un code qui calcule les permutations. Justement en ce qui concerne le code de MARCO, j'ai l'impression qu'il calcule les permutations parmi n éléments et pas les arrangements de p éléments parmi n.
Ami calmant, J.P |
| |
| |
| | | |
|
| | |
| |
Posté le 24 janvier 2012 - 17:37 |
Bonjour à tous,
Je bloque sur un problème similaire. Je souhaite lister tous les menus possibles avec tous ces éléments :
Entrées : Pâté, Tomates, Salade, Huîtres Plats : Tartiflette, Pâtes carbonara, Civet de lapin, Poulet Vins : Rouge, Blanc, Rosé Fromages : Livarot, Camembert, Gruyère, Compté Desserts : Mousse au chocolat, Tarte aux pommes, Fromage Blanc
Le nombre des éléments peut varier, mais le nombre de plats (entrée, plat, dessert) aussi, on peut parfois avoir en plus :
Café : Déca, Long, Thé, Tisane Digestif : Calvados, Eau de vie
Je résume : - nombre de plats non défini - nombre d'éléments par style de plat non défini
Toutes ces infos sont issues d'une table ayant pour colonnes : - nom de l'élément - nom du plat (niveau supérieur donc)
Je ne sais pas si j'ai été très clair dans mes propos, n'hésitez pas à me demander des infos supplémentaires.
Merci d'avance ! |
| |
| |
| | | |
|
| | |
| |
Posté le 24 janvier 2012 - 18:22 |
Bonjour à tous,
voici un algo qui permet de lister toutes les combinaisons possibles :
Je m'en sert pour faire la liste de tous les itinéraires possibles entre différents lieux
ncompt est un entier quelChoix est un entier comptPossibilité est un entier nbPossibilite est un entier=1 comptCycle est un entier nbCycle est un entier
//nombre de valeurs possibles (ou nombre de lieux de passage) nbChoix est un entier=5
//calcul du nombre de cas possibles POUR ncompt=1 _A_ nbChoix nbPossibilite=nbPossibilite*ncompt FIN
//initialisation du nombre de cycle avec le nombre de possibilités nbCycle=nbPossibilite
ListeSupprimeTout(Liste1)
//boucle sur le nombre de valeurs possibles //on ajoute les possibilités par colonne POUR ncompt=1 _A_ nbChoix //compteur pour savoir combien de fois on a ajouté une valeur possible comptCycle=1 //variable contenant le valeur possible en cours et que l'on va faire varier //ici on ajoute des chiffres quelChoix=0 //compteur sur le nombre de possibilités comptPossibilité=1 SI Liste1[comptPossibilité]~="" ALORS quelChoix=0 SINON quelChoix=Val(Droite(Liste1[comptPossibilité],1))+1 FIN //calcul du cycle de répétition d'une occurrence //pour les n-2 premières colonnes SI nbChoix-ncompt+1>0 ALORS nbCycle=nbCycle/(nbChoix-ncompt+1) //pour les 2 dernières colonnes SINON nbCycle=0 FIN //on ajoute chaque possibilité TANTQUE comptPossibilité<=nbPossibilite //on test si la valeur possible que l'on veut ajouter n'est pas déjà présente dans la combinaison TANTQUE ChaîneOccurrence(Liste1[comptPossibilité],quelChoix)>0 //si elle est déjà présente on passe à la suivante quelChoix++ //on test si l'on a pas dépassé la valeur max des valeurs possibles //auquel cas on repart à la première valeur possible SI quelChoix>nbChoix-1 ALORS quelChoix=0 FIN FIN //ajout de la valeur possible dans la liste Liste1[comptPossibilité]+=quelChoix //on incremente le compteur des possibilités comptPossibilité++ //on incremente le compteur de cycle comptCycle++ //si on atteint la valeur du cycle on change d'occurrence SI comptCycle>nbCycle ALORS comptCycle=1 quelChoix++ //on test si l'on a pas dépassé la valeur max des valeurs possibles //auquel cas on repart à la première valeur possible SI quelChoix>nbChoix-1 ALORS quelChoix=0 FIN FIN FIN FIN |
| |
| |
| | | |
|
| | |
| |
Posté le 25 janvier 2012 - 10:04 |
Bonjour,
Merci de votre réponse, cependant cela calcule les possibilités pour un tableau à une dimension non? |
| |
| |
| | | |
|
| | |
| |
Posté le 27 janvier 2012 - 13:00 |
Commenet adapter le souhait de Jérome avec ta proposition ?
Je souhaite lister tous les menus possibles avec tous ces éléments :
Entrées : Pâté, Tomates, Salade, Huîtres Plats : Tartiflette, Pâtes carbonara, Civet de lapin, Poulet Vins : Rouge, Blanc, Rosé Fromages : Livarot, Camembert, Gruyère, Compté Desserts : Mousse au chocolat, Tarte aux pommes, Fromage Blanc |
| |
| |
| | | |
|
| | |
| |
Posté le 30 janvier 2012 - 20:51 |
Personne n'a une idée?
J'ai un peu avancé : je génère mes chaines de caractères de façon aléatoire avec des hazard()
Quand le résultat est absent de ma base de données je l'enregistre.
ça fonctionne bien au début mais quand je tend vers 30000 possibilités... c'est la cata !
Il doit y avoir un autre moyen, plus simple et plus efficace, mais là ça sort de ma logique et je ne vois vraiment pas comment m'en sortir... |
| |
| |
| | | |
|
| | |
| |
Posté le 31 janvier 2012 - 13:35 |
Bonjour,
si une combi est du type : Entrées + Plats + Vins + Fromages + Desserts si chacun a 20 caractères : 1 combi = 5x20 = 100 caractères
donc tes 30 000 x 100 = 3 000 000 caractères
C'est très jouable de le faire en tableau en RAM au lieu d'utiliser une BDD où les accès disque relentissent considérablement les calculs.
Je ne crois pas qu'utiliser hazard() est une bonne idée pour faire tes combi, le mieux est de faire :
Entrées1 + Plats1 + Vins1 + Fromages1 + Desserts1 Entrées1 + Plats1 + Vins1 + Fromages1 + Desserts2 ..... Desserts3 ..... DessertsN Entrées1 + Plats1 + Vins1 + Fromages2 + Desserts1 Entrées1 + Plats1 + Vins1 + Fromages2 + Desserts2 ..... DessertsN Entrées1 + Plats1 + Vins1 + Fromages3 + Desserts1 ..... DessertsN
Entrées1 + Plats1 + Vins2 + Fromages1 + Desserts1 Entrées1 + Plats1 + Vins2 + Fromages1 + Desserts2
etc
Bon dev et A+ |
| |
| |
| | | |
|
| | |
| |
Posté le 31 janvier 2012 - 15:27 |
Bonjour Tony,
Merci de votre réponse. C'est "facile" (du moins dans ma logique) de suivre ton code, mais mon principal problème réside dans le fait que je ne sais pas à l'avance si je vais avoir des entrées, des digestifs,...
Si je savais que ma boucle comportais 5 "types de plats" ok, mais il se peut qu'à tout moment se rajoute un "type de plat"... |
| |
| |
| | | |
|
| | |
| |
Posté le 01 février 2012 - 17:47 |
J'ai avancé sur mon problème (du moins je crois). J'arrive a générer un tableau dont le contenu est :
Colonne 1 : les id des entrées Colonne 2 : les id des plats Colonne 3 : les id des fromages Colonne 4 : les id des desserts
Les X représentent les "cases" vides
0 0 0 0 1 1 1 1 X 2 X 2 X 3 X X X 4 X X X 5 X X X 6 X X X 7 X X X 8 X X X 9 X X X 10 X X X 11 X X X 12 X X X 13 X X X 14 X X X 15 X X X 16 X X X 17 X X
A partir de ce tableau il doit être "facile" d'évaluer les combinaisons possibles non? |
| |
| |
| | | |
|
| | |
| |
Posté le 01 février 2012 - 21:21 |
Bonjour Jérôme
4 pour imbriqués... c'est tout
Cordialement
-- Fabrice Harari Consultant WinDev, WebDev et WinDev Mobile International
Plus d'information sur http://fabriceharari.com/index_FR.html
On 01/02/2012 11:47, Jérôme FORKOD wrote:
J'ai avancé sur mon problème (du moins je crois). J'arrive a générer un tableau dont le contenu est :
Colonne 1 : les id des entrées Colonne 2 : les id des plats Colonne 3 : les id des fromages Colonne 4 : les id des desserts
Les X représentent les "cases" vides
0 0 0 0 1 1 1 1 X 2 X 2 X 3 X X X 4 X X X 5 X X X 6 X X X 7 X X X 8 X X X 9 X X X 10 X X X 11 X X X 12 X X X 13 X X X 14 X X X 15 X X X 16 X X X 17 X X
A partir de ce tableau il doit être "facile" d'évaluer les combinaisons possibles non?
|
| |
| |
| | | |
|
| | |
| |
Posté le 02 février 2012 - 11:02 |
Je ne comprends pas votre réponse, je cherche à sortir toutes les combinaisons possibles |
| |
| |
| | | |
|
| | |
| |
Posté le 02 février 2012 - 12:50 |
Bonjour,
J'ai pas très bien compris le problème. Il y a plusieurs catégorie d'aliment (Entrées ,Plats,Vins,Fromages,Camembert,Vin ,Desserts,Café,Digestif,...)
Je cite :
Je résume : - nombre de plats non défini - nombre d'éléments par style de plat non défini Café : Déca, Long, Thé, Tisane Digestif : Calvados, Eau de vie
Sa veux dire que tu pourrais avoir par une combinaison : Déca, Long, Tisane, Calvados, Eau de vie
Mais pas : Eau de vie, Tisane, Tisane |
| |
| |
| | | |
|
| | |
| |
Posté le 02 février 2012 - 18:19 |
Bonjour,
Si j'ai bien compris le poblème message ci-dessus. J'ai fait un petit algo. La BDD est composé de 2 fichiers Plat (IdPlat, Lib, IdType) Type (IdType, Lib)
J'ai pris les données que tu as fournis: Type : 1 Entrées 2 Plats 3 Vins 4 Fromages 5 Desserts 6 Café 7 Digestif
Et Plat : 1 Pâté 1 2 Tomates 1 3 Salade 1 4 Huîtres 1 5 Tartiflette 2 6 Pâtes carbonara 2 7 Civet de lapin 2 8 Poulet 2 9 Rouge 3 10 Blanc 3 11 Rosé 3 12 Livarot 4 13 Camembert 4 14 Gruyère 4 15 Compté 4 16 Mousse au chocolat 5 17 Tarte aux pommes 5 18 Fromage Blanc 5 19 Déca 6 20 Long 6 21 Thé 6 22 Tisane 6 23 Calvados 7 24 Eau de vie 7
Ce qui fait 21 233 664 combinaisons possible. (16*16*16*9*16*4)
Le problème, c'est qu'il y a trop de combinaisons possibles, personnelement je plante due a un manque de mémoire.
Voici le code (la fenêtre comporte un champ LISTE_TOTAL)
nVarPlatEnCours est un entier z est un entier TabTrav,TabType, TabTypePlat, TabListeCombi est un tableau de chaîne
Sablier()
POUR TOUT Type SUR IDType
TableauSupprimeTout(TabType) Ajoute(TabType,"")
HFiltre(Plat,IDPlat,hValMin,hValMax,"plat.idtype='"+Type.IDType+"'") HLitPremier(Plat) TANTQUE PAS HEnDehors(Plat)
TableauSupprimeTout(TabTypePlat)
Ajoute(TabTypePlat,Plat.Lib) nVarPlatEnCours=Plat.IDPlat HLitSuivant(Plat) TANTQUE PAS HEnDehors(Plat) z=TableauOccurrence(TabTypePlat) POUR x=1 A z Ajoute(TabTypePlat,TabTypePlat[x]+" - "+Plat.Lib) FIN HLitSuivant(Plat) FIN
POUR x=1 A TableauOccurrence(TabTypePlat) Ajoute(TabType,TabTypePlat[x]) FIN
HLitRecherchePremier(Plat,IDPlat,nVarPlatEnCours) HLitSuivant(Plat,IDPlat) FIN HDésactiveFiltre(Plat)
SI Type.IDType=6 ALORS SORTIR
SI TableauOccurrence(TabTrav)=0 ALORS TableauCopie(TabType,TabTrav) SINON TableauSupprimeTout(TabListeCombi) POUR x=1 A TableauOccurrence(TabTrav) POUR y=1 A TableauOccurrence(TabType) SI TabTrav[x]="" ALORS Ajoute(TabListeCombi,TabType[y]) SINON SI TabType[y]="" ALORS Ajoute(TabListeCombi,TabTrav[x]) SINON Ajoute(TabListeCombi,TabType[y]+" - "+TabTrav[x]) FIN FIN FIN TableauCopie(TabListeCombi,TabTrav) FIN FIN
TableauTrie(TabTrav)
POUR x=1 A TableauOccurrence(TabTrav) ListeAjoute(LISTE_Total,TabTrav[x]) FIN Sablier(Faux) |
| |
| |
| | | |
|
| | |
| |
Posté le 13 mars 2017 - 09:10 |
Bonjour,
Je ne sais pas si vous connaissez le jeu "RUZZLE" !!! - 16 lettres - 1 Fichier dictionnaire
Et ils arrivent en même pas 2 minutes à trouver les mots possibles de 2 lettres,3 lettres,4 lettres...etc... Et ils vous en donnent la liste !!!
C'est là que je comprends...que je resterai toute ma vie ....un débutant !!! |
| |
| |
| | | |
|
| | |
| |
Posté le 13 mars 2017 - 12:58 |
Bonjour
ca ne me parait pas vraiment un problème :
- le dictionnaire est chargé en mémoire dans une requête avant tout - ensuite on fait toutes les combinaisons possibles des 2 premières lettres, soit 16*15=2400 - pour chacune, on fait un hfiltre (ou une requête) sur la requête en mémoire et on trouve TOUS les mots possibles qui commencent par les 2 lettres - ensuite on parcours chaque résultat et on ELIMINE les pas bons (en comparant chaque caractère en boucle avec les 14 caractères restants), ce qui va VITE éliminer la majorité des mots - en sortie de cette boucle, on a tous les mots qui correspondent aux 16 lettres
et comme tout ça se fait en mémoire, ca devrait tenir sans problème dans tes 2 minutes
Cordialement
-- Fabrice Harari Consultant WinDev, WebDev et WinDev Mobile International
A votre disposition : WXShowroom.com, WXReplication (open source) et maintenant WXEDM (open source)
Plus d'information sur http://fabriceharari.com
Le 3/13/2017 à 3:10 AM, "ÿÿÿÿÿÿÿÿÿÿÿÿ" a écrit :
Bonjour,
Je ne sais pas si vous connaissez le jeu "RUZZLE" !!! - 16 lettres - 1 Fichier dictionnaire
Et ils arrivent en même pas 2 minutes à trouver les mots possibles de 2 lettres,3 lettres,4 lettres...etc... Et ils vous en donnent la liste !!!
C'est là que je comprends...que je resterai toute ma vie ....un débutant !!! |
| |
| |
| | | |
|
| | |
| |
Posté le 18 mai 2017 - 19:41 |
Bonjour a tous Je suis entrain de develloper une application combinatoire mais je suis bloqué pck ke ne saiw pas comment y parvenir .Svp aidez moi Cordialement |
| |
| |
| | | |
|
| | | | |
| | |
|