Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2364 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

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

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

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

n°1732310
backdafuck​up
Back to da old skool
Posté le 15-05-2008 à 16:53:34  profilanswer
 

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
mood
Publicité
Posté le 15-05-2008 à 16:53:34  profilanswer
 

n°1732329
backdafuck​up
Back to da old skool
Posté le 15-05-2008 à 17:29:07  profilanswer
 

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 ?

n°1732337
R3g
fonctionnaire certifié ITIL
Posté le 15-05-2008 à 17:35:33  profilanswer
 

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.
n°1732341
xtof_83
Freeride Spirit
Posté le 15-05-2008 à 17:37:02  profilanswer
 

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

Message cité 1 fois
n°1732342
flo850
moi je
Posté le 15-05-2008 à 17:37:21  profilanswer
 


 
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

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

n°1732343
backdafuck​up
Back to da old skool
Posté le 15-05-2008 à 17:37:41  profilanswer
 

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
n°1732346
backdafuck​up
Back to da old skool
Posté le 15-05-2008 à 17:41:32  profilanswer
 

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 :)

n°1732347
flo850
moi je
Posté le 15-05-2008 à 17:43:50  profilanswer
 

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;
 
 
 


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

n°1732348
backdafuck​up
Back to da old skool
Posté le 15-05-2008 à 17:44:22  profilanswer
 

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]  
 
 
 

n°1732349
masklinn
í dag viðrar vel til loftárása
Posté le 15-05-2008 à 17:45:22  profilanswer
 

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

---------------
I mean, true, a cancer will probably destroy its host organism. But what about the cells whose mutations allow them to think outside the box by throwing away the limits imposed by overbearing genetic regulations? Isn't that a good thing?
mood
Publicité
Posté le 15-05-2008 à 17:45:22  profilanswer
 

n°1732351
R3g
fonctionnaire certifié ITIL
Posté le 15-05-2008 à 17:45:48  profilanswer
 

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


---------------
Au royaume des sourds, les borgnes sont sourds.
n°1732358
backdafuck​up
Back to da old skool
Posté le 15-05-2008 à 17:56:42  profilanswer
 

?
 
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
n°1732360
masklinn
í dag viðrar vel til loftárása
Posté le 15-05-2008 à 18:13:12  profilanswer
 

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

---------------
I mean, true, a cancer will probably destroy its host organism. But what about the cells whose mutations allow them to think outside the box by throwing away the limits imposed by overbearing genetic regulations? Isn't that a good thing?
n°1732368
backdafuck​up
Back to da old skool
Posté le 15-05-2008 à 18:28:47  profilanswer
 

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
n°1732370
masklinn
í dag viðrar vel til loftárása
Posté le 15-05-2008 à 18:35:15  profilanswer
 

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

---------------
I mean, true, a cancer will probably destroy its host organism. But what about the cells whose mutations allow them to think outside the box by throwing away the limits imposed by overbearing genetic regulations? Isn't that a good thing?
n°1732373
backdafuck​up
Back to da old skool
Posté le 15-05-2008 à 18:46:59  profilanswer
 

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
n°1732376
masklinn
í dag viðrar vel til loftárása
Posté le 15-05-2008 à 19:02:10  profilanswer
 

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

---------------
I mean, true, a cancer will probably destroy its host organism. But what about the cells whose mutations allow them to think outside the box by throwing away the limits imposed by overbearing genetic regulations? Isn't that a good thing?
n°1732462
sligor
Posté le 15-05-2008 à 23:18:21  profilanswer
 

demain soir je tenterais bien de faire ce truc en vhdl

Spoiler :

j'ai une vie passionnante [:cerveau merdocu]

n°1732566
backdafuck​up
Back to da old skool
Posté le 16-05-2008 à 09:51:45  profilanswer
 

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]

n°1732572
backdafuck​up
Back to da old skool
Posté le 16-05-2008 à 10:08:13  profilanswer
 

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

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

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

 

Sujets relatifs
afficher des image stocker dans bdd mysqlALGO Génétique...
[Algo] Question d'ultra débutant[Algo] Calcul de distance entre deux rectangles
stocker une image à partir d'un contexte mémoireexo d'algo aide s'il vous pait
[Algo] de recherche[Algo WEB] Suppression de fichiers générés pour téléchargement unique
Où stocker une variable transitoire ? [Résolu]ecrire un algo
Plus de sujets relatifs à : Algo -> Dénombrer toutes les possibilités et les stocker

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.142 secondes

Copyright © 1997-2025 Groupe LDLC (Signaler un contenu illicite / Données personnelles)