Discussion :

[MatP]

Bonjour,

Je chercherais le moyen de trouver toutes les combinaisons possibles (dans l'ordre et le désordre) que je peux faire à partir d'un array de N objet, sauf ceux qui sont identiques de gauche à droite et de droite à gauche, j'en veux qu'un seul.

Par exemple avec { obj0, obj1, obj2 }, je voudrais créer les arrays suivant:


{ obj0 }
{ obj0, obj1 }
{ obj0, obj2 }
{ obj0, obj1, obj2 }
{ obj0, obj2, obj1 }

{ obj1 }
{ obj1, obj0 }
{ obj1, obj2 }
{ obj1, obj0, obj2 }
{ obj1, obj2, obj0 }

{ obj2 }
{ obj2, obj1 }
{ obj2, obj0 }
{ obj2, obj0, obj1 }
{ obj2, obj1, obj0 }

En fait, ceux qui sont barrés, ça me dérange pas qu'ils apparaissent si ça simplifie le code. L'important n'est pas tant la performance que le fait que ce soit simple à comprendre. J'aurai rarement plus de 5 ou 6 items. Si ça se rend à 12, je patienterai plus.

S.v.p tenir compte que je dois faire ça en VBA.

En fait, si j'élabore encore plus, les objets sont des points. Je veux pouvoir créer tous les polygones simples possibles avec ces points dont tous les autres points sont à l'intérieur. Il y a aussi une autre variables qui fait que j'ajoute 2 ou 3 points à chacun des polygones dont leurs coordonnées sont variables et dépendent du premier et dernier point du polygone initial. Quoiqu'il en soit, si je peux faire toutes les combinaisons possibles, je pourrai gérer après si le polygone formé est valide ou non.

Merci

[prgasp77]

Salut. Imaginons que tu saches construire une telle liste de tableau pour N items :

[
{A, B, C},
{B, C, A},
...
]

Pour construire une liste similaire pour N+1 items, il suffit, pour chaque tableau de ta liste (dans l'exemple, pour chaque ligne), d'insérer le N+1-ième item à chaque emplacement possible :

[
{D, A, B, C},{A, D, B, C},{A, B, D, C},{A, B, C, D},
{D, B, C, A},{B, D, C, A},{B, C, D, A},{B, C, A, D},
...
]

Ainsi, du fait que tu n'as qu'un faible nombre d'items, je propose une solution récursive :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
fonction arrangements(l : liste d'item)
Si taille de l = 1 Alors
   retourner l
Sinon
   Soient tete : item et queue : liste d'item telles que tete+queue=l
   Soit resultat : liste de (liste d'item)
   l' = arrangements(queue)
   Pour chaque liste arrangement de l'
      Pour chaque item i de arrangement
         Ajouter la liste arrangement[0..i-1]+tete+arrangement[i..fin] à resultat
      Fin Pour
   Fin Pour
   retourner resultat
Fin Si

[MatP]

Hmmm malheureusement je ne sais pas faire la première étape. Et j'ai de la misère à suivre ton pseudocode. Par contre, ton explication m'aide un peu à comprendre la logique que je devrais envisager, je vais réfléchir davantage à tout ça.

[prgasp77]

Quelle première étape ?

Si d'une part tu sais résoudre ton problème pour un unique objet, et
si d'autre part à partir de la résolution pour N objets tu sais résoudre pour N+1 objets,

alors, tu sais résoudre le problème dans tous les cas. C'est ce qu'on appelle de la récursivité. Je te conseille une petite recherche à partir de ce mot.

Cdlt,

[prgasp77]

Et MERCI ça ne serait pas de trop !