Algo -> Dénombrer toutes les possibilités et les stocker

Algo -> Dénombrer toutes les possibilités et les stocker - Algo - Programmation

Marsh Posté le 15-05-2008 à 16:53:34    

Salut à tous,
 
Bon, j'ai pas pour habitude de demander pour un algo, mais là je perds pied, pis ça fait très longtemps que j'ai pas fait d'algos de ce type, mais il se trouve que j'en ai besoin...
 
J'explique le souci.
 
J'ai en entrée une liste d'options pour un article, chaque option ayant plusieurs choix possible.
Je dois dénombrer toutes les combinaisons possibles d'option pour un article avec cet algo.
 
Exemple (les choix d'option sont des numéros) :
 
Pour l'article 1 j'ai la chose suivante :  
 
4|5|          OPTION 0
13|14|       OPTION 1
60|61|       OPTION 2
28|29|30|   OPTION 3
35|36|37|   OPTION 4
 
Je dois donc trouver toutes les combinaisons possibles.
Exemple de combinaison :  
4 - 13 - 60 - 28 - 35
4 - 14 - 60 - 28 - 35
etc
 
Voilà, et là je commence à m'arracher les cheveux...
 
Un ptit coup de main rapide ? (j'ai l'impression que c'est un cas d'école et que j'ai l'air ridicule, c'est horrible.....)
 
Faut faire quoi ? fonction récursive ?

Message cité 1 fois
Reply

Marsh Posté le 15-05-2008 à 16:53:34   

Reply

Marsh Posté le 15-05-2008 à 17:29:07    

Pour faire plus simple et reformuler :  
 
J'ai une série de n tableaux comprenant un nombre x d'éléments (pouvant être différents bien sûr)
 
je voudrais arriver à stocker toutes les combinaisons possibles de ces n tableaux.
 
Tain même en écrivant je trouve ça pas clair...
Ya quelqu'un qui a compris ce que je voulais faire au moins ?

Reply

Marsh Posté le 15-05-2008 à 17:35:33    

Tu connais le nombre de choix pour chaque option ? Si oui chaque option est un tableau contenant les choix, et tu parcours les tableaux dans 5 boucles imbriquées pour générer les combinaisons...

 

et, comme dirait schnapsmann, c'est bidon, c'est quoi qui te pose problème au juste ?

Message cité 1 fois
Message édité par R3g le 15-05-2008 à 17:36:39

---------------
Au royaume des sourds, les borgnes sont sourds.
Reply

Marsh Posté le 15-05-2008 à 17:37:02    

Ton truc c'est par colonnes ?
 
tu peux avoir  
 
30 - 37
ou du genre
14 - 61 - 29 - 37 ?

Message cité 1 fois
Reply

Marsh Posté le 15-05-2008 à 17:37:21    


 
matrice => un tableau a deux dimension matrice[0] contient les choix a afrie en premiere , matrice[1] les seconds...

Code :
  1. fonction pwet(tableau choixDejaFait,  matrice possibilites)
  2. {
  3.       nbChoix = taille( choixDejaFait );
  4.       if(taille(possibilite) > nbchoix)
  5.           pour i allant de 0 a taille(possibilites[nbChoix+1])
  6.                 nouveauChoix = choixDejaFait;
  7.                 ajoute  possibilites[nbChoix+1][i] dans nouveauChoix
  8.                 pwet( nouveauChoix ,  possibilites);
  9.       sinon
  10.           affiche(choixDejaFait)
  11.    
  12. }


 
un truc comme ca ?

Message cité 1 fois

---------------

Reply

Marsh Posté le 15-05-2008 à 17:37:41    

R3g a écrit :

Tu connais le nombre de choix pour chaque option ? Si oui chaque option est un tableau contenant les choix, et tu parcours les tableaux dans 5 boucles imbriquées pour générer les combinaisons...
 
et, comme dirait schnapsmann, c'est bidon, c'est quoi qui te pose problème au juste ?


 
 
Ce nombre est malheureusement variable.... Un article peut avoir plus ou moins d'options....
 
De même, selon l'article, chaque option possède plus ou moins de choix...
 
Donc je peux rien faire de fixe, c'est pour ça que je pensais à de la récursivité....


Message édité par backdafuckup le 15-05-2008 à 17:39:44
Reply

Marsh Posté le 15-05-2008 à 17:41:32    

flo850 a écrit :


 
matrice => un tableau a deux dimension matrice[0] contient les choix a afrie en premiere , matrice[1] les seconds...

Code :
  1. fonction pwet(tableau choixDejaFait,  matrice possibilites)
  2. {
  3.       nbChoix = taille( choixDejaFait );
  4.       if(taille(possibilite) > nbchoix)
  5.           pour i allant de 0 a taille(possibilites[nbChoix+1])
  6.                 nouveauChoix = choixDejaFait;
  7.                 ajoute  possibilites[nbChoix+1][i] dans nouveauChoix
  8.                 pwet( nouveauChoix ,  possibilites);
  9.       sinon
  10.           affiche(choixDejaFait)
  11.    
  12. }


 
un truc comme ca ?


 
Bon, je suis pas sûr d'avoir tout capté....
Tu peux détailler un peu tes paramètres stp ? merci :)

Reply

Marsh Posté le 15-05-2008 à 17:43:50    

au debut , choix deja fait est un tableau vide  
 
 
possibilites[0][0] = 4;
possibilites[0][1] = 5;
 
possibilites[1][0] = 13;
possibilites[1][1] = 14;
 
possibilites[2][0] = 60;
possibilites[2][1] = 61;
 
possibilites[3][0] = 28;
possibilites[3][1] = 29;
possibilites[3][2] = 30;
 
possibilites[3][0] = 35;
possibilites[3][1] = 36;
possibilites[3][2] = 37;
 
 
 


---------------

Reply

Marsh Posté le 15-05-2008 à 17:44:22    

xtof_83 a écrit :

Ton truc c'est par colonnes ?
 
tu peux avoir  
 
30 - 37
ou du genre
14 - 61 - 29 - 37 ?


 
Non, tu dois avoir un élément de chaque option à chaque fois.
Comme les exemples que j'ai donnés :  
 
4 - 13 - 60 - 28 - 35  
4 - 14 - 60 - 28 - 35  
 
dans mon exemple général (et si j'ai bien apris mes leçons de proba)  :  
 
4|5|
13|14|
60|61|
28|29|30|
35|36|37|
 
on a donc 2 x 2 x 2 x 3 x 3 possibilités = 72 combinaisons possibles....
 
Je commence à m'arracher les cheveux un par un...  [:violito]  
 
 
 

Reply

Marsh Posté le 15-05-2008 à 17:45:22    

backdafuckup a écrit :

Faut faire quoi ? fonction récursive ?


Ca se fait relativement simplement en utilisant un algo récursif super naïf, soit pour construire un arbre (le plus simple) soit pour construire une liste de listes.

 

Pour le second cas, en Python ça devrait donner un truc du genre:

Code :
  1. def combine(options):
  2.     if not options: return [[]]
  3.     out = []
  4.     for item in options[0]:
  5.         for suboption in combine(options[1:]):
  6.             out.append([item] + suboption)
  7.     return out


mais je suis certain que e.g. 0x90 pourrait sortir un algo plus propre :D


Message édité par masklinn le 15-05-2008 à 17:48:08

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 15-05-2008 à 17:45:22   

Reply

Marsh Posté le 15-05-2008 à 17:45:48    

Mais y'a rien de compliqué là, c'est quoi qui te bloque ?


---------------
Au royaume des sourds, les borgnes sont sourds.
Reply

Marsh Posté le 15-05-2008 à 17:56:42    

?
 
Bah faut croire que j'ai tout perdu en algo alors... Et que je sais plus faire que des lamentables interfaces web.... mais je bloque oui....
 
Je suis en train de tester l'algo de flo850....
 
Masklinn> Je sais pas lire le python... T'as plus simple ? genre je sais pas moi... vb ?

Message cité 1 fois
Reply

Marsh Posté le 15-05-2008 à 18:13:12    

backdafuckup a écrit :

Masklinn> Je sais pas lire le python... T'as plus simple ? genre je sais pas moi... vb ?


Je crois que ça va pas être possible non.

Message cité 1 fois

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 15-05-2008 à 18:28:47    

masklinn a écrit :


Je crois que ça va pas être possible non.


 
Non je déconnais hein.... Mais tout autre langage "humain" serait acceptable.... (Je ne connais pas du tout la syntaxe python)
 
Flo850> Ton algo donne ça comme résultat :
 
4|13|60|28|35|
4|13|60|28|35|36|
4|13|60|28|35|36|37|
4|13|60|28|35|36|37|29|
4|13|60|28|35|36|37|29|30|
4|13|60|28|35|36|37|29|30|61|
4|13|60|28|35|36|37|29|30|61|14|
4|13|60|28|35|36|37|29|30|61|14|5|
 
 
Ce qui fait que donc ce n'est pas bon... J'ai traduit ta fonction en vb.net, mais j'ai ptet mal fait qqc :  
 

Code :
  1. Sub Pwet(ByVal choixDejaFait As Collection, ByVal possibilites As Collection)
  2.         Dim nouveauchoix As New Collection
  3.         Dim Nbchoix As Integer
  4.         nbChoix = choixDejaFait.Count
  6.         If (possibilites.Count > Nbchoix) Then
  7.             For Each elt As Object In possibilites(Nbchoix + 1)
  8.                 nouveauchoix = choixDejaFait
  9.                 'If nouveauchoix.Count > 0 Then
  10.                 ' nouveauchoix.Remove(nouveauchoix.Count)
  11.                 'End If
  12.                 nouveauchoix.Add(elt)
  13.                 Call Pwet(nouveauchoix, possibilites)
  14.             Next
  15.         Else
  16.             For Each elt As Object In choixDejaFait
  17.                 lbl_test.Text &= elt.ToString & "|"
  18.             Next
  19.             lbl_test.Text &= "<br />"
  20.         End If
  21.     End Sub


 
Voilà... merci de votre aide.... je sens qu'on est pas loin  [:tekways]

Message cité 1 fois
Reply

Marsh Posté le 15-05-2008 à 18:35:15    

backdafuckup a écrit :

 

Non je déconnais hein.... Mais tout autre langage "humain" serait acceptable.... (Je ne connais pas du tout la syntaxe python)


Elle est pas bien compliquée.

 

def permet de définir une fonction, [] crée un tableau ([[]] crée un tableau vide dans un tableau), if c'est un test booléen, not ça inverse un booléen, for a in b ça permet d'itérer dans la collection b, et a.append(b) ça ajoute b à la fin de a quand a est un tableau.

 

edit: ah oui, et a[b] ça renvoie l'élément situé à l'index b de la collection a, et a[b:] ça renvoie une slice, un array contenant tous les éléments de l'array a à partir de l'index b inclus (et jusqu'à la fin)


Message édité par masklinn le 15-05-2008 à 18:36:35

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 15-05-2008 à 18:46:59    

Il manque une réinitialisation qqpart sur l'algo de flo, mais j'arrive pas à trouver.....
 
Masklinn > et le append([item] + suboption) ça veut dire quoi ?
Sympa la slice, mais je traduis ça comment moi en vb.net ????
 

Message cité 1 fois
Reply

Marsh Posté le 15-05-2008 à 19:02:10    

backdafuckup a écrit :

Il manque une réinitialisation qqpart sur l'algo de flo, mais j'arrive pas à trouver.....

 

Masklinn > et le append([item] + suboption) ça veut dire quoi ?


[item] crée une liste d'un élément
list + list ça combine deux listes pour en créer une 3e.
Donc [item] + suboption ça ajoute item au début de la liste "suboption", mais en créant une nouvelle liste et non en modifiant suboption.

backdafuckup a écrit :

Sympa la slice, mais je traduis ça comment moi en vb.net ????


Ben une méthode genre SubList, connerie du style [:spamafote]

 



Message édité par masklinn le 15-05-2008 à 19:02:16

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody
Reply

Marsh Posté le 15-05-2008 à 23:18:21    

demain soir je tenterais bien de faire ce truc en vhdl

Spoiler :

j'ai une vie passionnante [:cerveau merdocu]

Reply

Marsh Posté le 16-05-2008 à 09:51:45    

Bon, je galère toujours...
 
je remets mon code VB (dsl Masklinn, j'arrive pas à traduire ton code en VB, ça fait planter le serveur :) )
pour la fonction de flo850
 

Code :
  1. Sub Pwet(ByVal choixDejaFait As Collection, ByVal possibilites As Collection)
  2.         Dim Nbchoix As Integer
  3.         nbChoix = choixDejaFait.Count
  5.         If (possibilites.Count > Nbchoix) Then
  6.             For Each elt As Object In possibilites(Nbchoix + 1)
  7.                 Dim nouveauchoix As New Collection
  8.                 nouveauchoix = choixDejaFait
  9.                 nouveauchoix.Add(elt)
  10.                 Call Pwet(nouveauchoix, possibilites)
  11.             Next
  12.         Else
  13.             For Each elt As Object In choixDejaFait
  14.                 lbl_test.Text &= elt.ToString & "|"
  15.             Next
  16.             lbl_test.Text &= "<br />"
  17.         End If
  18.     End Sub


 
voici le résultat produit :  
 
4|13|60|28|35|
4|13|60|28|35|36|
4|13|60|28|35|36|37|
4|13|60|28|35|36|37|29|
4|13|60|28|35|36|37|29|30|
4|13|60|28|35|36|37|29|30|61|
4|13|60|28|35|36|37|29|30|61|14|
4|13|60|28|35|36|37|29|30|61|14|5|
 
Et ça s'arrete la...
 
Ya donc une réinitialisation qui foire. le truc c'est que si je mets un  
nouveauchoix.clear()
 
Ca fait planter le serveur....
 
Je suis pas très bon en récursivité, et la je continue de galérer pour des conneries....
 
Merci  [:aras qui rit]

Reply

Marsh Posté le 16-05-2008 à 10:08:13    

Ca y est !!!!!!!!!
 
C'était bien un pb de réinitialisation...
Voici le code final en vb.net donc :  
 

Code :
  1. Sub Pwet(ByVal choixDejaFait As Integer(), ByVal possibilites As Collection)
  2.         Dim Nbchoix As Integer
  4.         Try
  5.             Nbchoix = choixDejaFait.Length
  6.         Catch
  7.             Nbchoix = 0
  8.         End Try
  10.         If (possibilites.Count > Nbchoix) Then
  11.             For Each elt As Object In possibilites(Nbchoix + 1)
  12.                 Dim nouveauchoix As Integer()
  13.                 nouveauchoix = choixDejaFait
  14.                 Try
  15.                     ReDim Preserve nouveauchoix(UBound(choixDejaFait) + 1)
  16.                 Catch
  17.                     ReDim Preserve nouveauchoix(0)
  18.                 End Try
  19.                 nouveauchoix(UBound(nouveauchoix)) = elt
  20.                 'nouveauchoix.Add(elt)
  22.                 Call Pwet(nouveauchoix, possibilites)
  23.             Next
  24.         Else
  25.             size += 1
  26.             lbl_test.Text &= size & " : "
  27.             For Each elt As Object In choixDejaFait
  28.                 lbl_test.Text &= elt.ToString & "|"
  29.             Next
  30.             lbl_test.Text &= "<br />"
  32.         End If
  33.     End Sub


 
 
Merci à tous, Masklinn et flo pour vos algos, et aux autres aussi pour m'avoir aidé.
 
A bientôt !


Message édité par backdafuckup le 16-05-2008 à 10:08:49
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed