Discussion :

[xorsx]

bonjour à tous,

ca fait pas mal d'heure que j'essaye d'obtenir un algo en pascal qui permet d'avoir tous les polygones possibles qui peuvent etre construits à partir du liste de points (qui dans dans une liste p).

exemple : j'ai ma liste p qui contient les points {2,3,4,7,1}
et je voudrais obtenir les différentes combinaisons possibles :
2347
234
2341
2471,etc..

j'essaye de faire un algorithme récursif;


merci de m'aider;;


ps: j'ai vu un sujet là dessus mais ca correspondait pas trop vu que je souhaiterais le faire en récursif..

[millie]

exemple : j'ai ma liste p qui contient les points {2,3,4,7,1}

Tu es sûr que tu ne souhaites que ceux-là ? Il ne faut pas également déterminer d'autres points que tu peux construire (genre au compas et à la régle) .

EDIT : Excuses, j'avais donné un mauvais lien, j'avais pas fait attention à un petit détail Ton algorithme ressemble à quoi pour l'instant ?

Une indication, imagines que tu as déjà l'algorithme pour faire cela pour n éléments (il y a donc p listes {L1,...., Lp} qui correspondent à tous les polygones)

Alors pour n+1 éléments {e_1, ... e_n, e_n+1}, les possibilités seront :

{L1, .... Lp} U {L1U{e_n+1}, L2 U {e_n+1}, ..... Lp U {e_n +1}}

Donc maintenant, à toi de faire jouer la récursivité pour y arriver

[millie]

Voilà, hop, comme c'était un algorithme récursif, je l'ai fait en camL (et oui, je vais pas te le donner en Pascal, ce serait trop simple), peut-être que ça pourra t'aider :

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
16
17
18
19
20
 
(* ajoute l'élément element à la liste de liste :
 par exemple :
  ajoute [[1;2];[3;4]] 5 donne
  [[5;1;2];[5;3;4]]
 *)
let rec ajoute liste element=
 match liste with
 [] -> []
 | a::reste -> 
      (element::a)::(ajoute reste element);;
 
let rec f lpolygone lelement = 
 match lelement with
   [] -> lpolygone
  | element::lreste ->
       f (lpolygone@(ajoute lpolygone element)) lreste;;
 
 
f [[]] [1;2;3;4];;

Le symbole [] correspond à la liste vide, @ correspond à la concaténation de deux liste, le symbole :: correspondent à la concaténation d'un élément et d'une liste.

Par exemple :

Code :

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

1
2
3
4
5
6
7
 
f [[]] [1;2;3;4];;
 
fournit :
 
[[]; [1]; [2]; [2; 1]; [3]; [3; 1]; [3; 2]; [3; 2; 1]; [4]; [4; 1]; 
  [4; 2]; [4; 2; 1]; [4; 3]; [4; 3; 1]; [4; 3; 2]; [4; 3; 2; 1]]

[xorsx]

mais avec le caml j'voi pas trop comment faire...

en fait, moi j'ai deja un polygone p avec un certain nombre de points n par exemple;
et je souhaite construire tous les autres polygones possibles à partir de p (et avec au moins 3 points puisqu'un polygone = au moins 3 pts)

donc pour ta liste [1;2;3;4] ::: il fodrait que j'ai

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
etc...

[millie]

et je souhaite construire tous les autres polygones possibles à partir de p (et avec au moins 3 points puisqu'un polygone = au moins 3 pts)

Ca dépend de la définition que tu prends de polygone.

donc pour ta liste [1;2;3;4] ::: il fodrait que j'ai

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2

C'est parce que je ne considérais pas l'ordre important, puisqu'en général, on ne garde que les polygones convexes ou concaves (en fait non croisé). Donc je donnais un ensemble de sommet dont il fallait réorganiser les arêtes suivants la topologie des points (un polygone est à la fois un ensemble de sommet et un ensemble d'arêtes)


Dans ce cas, regardes à permutation ou à n-tuples dans les liens de Jean-Marc :

http://www.developpez.net/forums/sho...62#post1586162

Sinon, mon algorithme peut être adapté assez rapidement avec des réunions d'ensemble, mais l'efficacité sera bof.

EDIT : Donne nous l'algorithme que tu as pour l'instant