Discussion :

[Synesthesia]

Bonjour tout le monde,
J'ai cherché un peu partout dans le forum Algorithme, dans les divers tutoriaux et FAQs mais je n'ai rien trouvé qui pourrait satisfaire mon problème, c'est pourquoi j'ai crée un nouveau sujet.

Je me prends la tête depuis plusieures heures à essayer de penser un algorithme qui me permettrait de calculer toutes les combinaisons possibles de plusieurs élements par rapport à une liste d'élément choisie, chaque combinaison.

Un petit exemple pour que ce soit plus clair :

Dans mes éléments j'ai des objets et des packs d'objets :
Objet 1, Objet 3, Objet 5, Pack 1, Pack 2, Pack 3.

Chaque pack contient plusieurs objets :
Pack 1 contient Objet 1 et Objet 3.
Pack 2 contient Objet 2 et Objet 3.
Pack 3 contient Objet 4 et Objet 5.

Ensuite j'ai une liste d'objets demandés : Objet 1, Objet 3 et Objet 5.

Mon algorithme doit calculer toutes les combinaisons de packs et/ou d'objets pour réussir à satisfaire tous les objets demandées, dans le cas présent une combinaison possible serait : Pack 1 + Objet 5.
Une seconde combinaison possible serait : Pack 1 + Pack 3.
Une troisième combinaison possible serait : Objet 1 + Objet 3 + Pack 3.
Une quatrième combinaison possible serait : Objet 1 + Objet 3 + Objet 5.
etc...

Par contre il est impossible de se retrouver avec Pack 1 + Pack 1 (il ne doit pas y avoir de doublon au niveau de la combinaison).

C'est peut-être pas très très très clair, mais je ne vois pas comment détaillé davantage le problème.

Merci d'avance !

Synesthesia.

[Nemerle]

Dans mes éléments j'ai des objets et des packs d'objets :
Objet 1, Objet 2, Objet 3, Objet 4, Objet 5, Pack 1, Pack 2, Pack 3.

Chaque pack contient plusieurs objets :
Pack 1 contient Objet 1 et Objet 3.
Pack 2 contient Objet 2 et Objet 3.
Pack 3 contient Objet 4 et Objet 5.

Ensuite j'ai une liste d'objets demandés : Objet 1, Objet 3 et Objet 5.

Mon algorithme doit calculer toutes les combinaisons de packs et/ou d'objets pour réussir à satisfaire tous les objets demandées, dans le cas présent une combinaison possible serait : Pack 1 + Objet 5.
Une seconde combinaison possible serait : Pack 1 + Pack 3.
Une troisième combinaison possible serait : Objet 1 + Objet 3 + Pack 3.
Une quatrième combinaison possible serait : Objet 1 + Objet 3 + Objet 5.
etc...

Si je comprends: tu veux toutes les "combinaisons" contenant objet1,objet3 et objet5

C'EST CA???

[Synesthesia]

Ah euh.. oui effectivement c'est ça, c'est marrant comment tu as résumé tout le problème en 1 ligne. :p

Synesthesia.

[Nemerle]

Imaginons que tu aies x objets.

Je pars du principe que tu sais sélectionner p éléments, qu'ils soient objets ou packs.
Pour une sélection E1,...,Ep donnée, tu initialises un vecteur d'entier n[1],..,n[x] à 0, et tu parcours tes Ei:
- si c'est un objet tu fais n[j]=n[j]+1 si Ei est l'objet Objet(j)
- si c'est un pack tu fais n[j]=n[j]+1 pour tous les Objets(j) de ce pack

A la fin, tu regardes la valeur des n[]: il faut que
- tous les n[i]<=1 pour tout i
- les n[j]=1 lorsque tu veux que ta sélection contienne Objet(j)

[Synesthesia]

J'ai un peu de mal à saisir ta réponse Nemerle, je n'arrive pas vraiment à me l'imaginer, peux-tu donner un exemple ? avec du pseudo-code par exemple

Je vais quand même continuer à essayer de comprendre !

Merci d'avance.

[Edit] En fait je pense avoir saisi, mais je ne suis pas sûr que cela me donne toutes les combinaisons possibles pour réunir les X objets dont j'ai besoin (Objet 1, Objet 3 et Objet 5 en l'occurence dans l'exemple).

J'ai plus l'impression que ça va me sortir tous les packs/objets qui contiennent au moins un de mes objets, alors qu'en fait il faudrait que je trouve les combinaisons de packs/objets qui réunissent la totalité des objets dont j'ai besoin.

D'ailleurs, tous les objets et packs présent contiennent au moins un objet dont j'ai besoin (j'ai dû oublier de le préciser dans mon post initial et du coup mon premier exemple semble faux..).

J'ai corrigé l'exemple qui se trouve dans mon post initial.

Synesthesia.

[Nemerle]

Il y a x objets/packs possibles. Supposons que l'on veut que les résultats contiennent les k Objets suivants: Objet(o[1]),..,Objet(o[k]). Pour tout p<=x, pour toute sélection E1,...,Ep donnée, on note
- Ei.obj=j tel que Ei=Objet(j) ou =0 si Ei est un pack
- Ei.pack=j tel que Ei=Pack(j) ou =0 si Ei est un objet

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
pour i de 1 à x {n[i]=0}
pour i de 1 à p {
   si Ei.obj>0{
      n[Ei.obj]=n[Ei.obj]+1
   }
   sinon{    // c'est un pack
      pour tout j de Pack(Ei.pack){
         n[j]=n[j]+1
       }
   }
}
booléen doublon=false, ok=true
pour i de 1 à x {si n[i]>1 alors doublon=true}
pour i de 1 à k {si n[o[i]]=0 alors ok=false}
Si (doublon=false et ok=true) alors { C'EST BON!!!}

A toi de parcourir tous les candidats E1,...,Ep, pour tout p<x ==> y a plein de sujet dans ce forum, fait une recherche.

[Nemerle]

J'ai plus l'impression que ça va me sortir tous les packs/objets qui contiennent au moins un de mes objets, alors qu'en fait il faudrait que je trouve les combinaisons de packs/objets qui réunissent la totalité des objets dont j'ai besoin.

Synesthesia.

NON dès qu'un objet manque, la sélection en cours est écartée...

[coyotte507]

j'ai du mal à saisir ton code

pour i de 1 à x {n[i]=0}
pour i de 1 à p

x correspond au nombre d'objets?
p au nombre de packs?
n au tableau qui dit quelle est la selection?

pour i de 1 à k {si n[x[i]]=0 alors ok=false}

x était un entier dans la première ligne, ici c'est un tableau?

que veut dire k?


Merci de répondre à mes questions

[Nemerle]

j'ai du mal à saisir ton code



x correspond au nombre d'objets?
p au nombre de packs?
n au tableau qui dit quelle est la selection?


x était un entier dans la première ligne, ici c'est un tableau?

que veut dire k?


Merci de répondre à mes questions

T'as raison pour les x[], j'avais fait une MAJ un peu rapide => Je viens de mettre à jour proprement mon post.

x est le nombre d'obj+packs, p le nbre d'éléments choisi dans les obj+packs.

[coyotte507]

Merci de m'avoir éclairé

[Nemerle]

you're welcome

Est-ce resolu??????