Discussion :

[LlufRuS]

Bonjour a tous,
voilà j'ai un peu honte de ma question mais je dois avouer commencer à attraper un bon mal de crane qui m'empeche d'y voir clair donc je me lance ici en ésperant y voir un petit peu plus clair.
Problème : je dispose d'un polygone (n points), je souhaite trouver une enveloppe convexe; de plusieurs façons différentes (comparaison de complexité.).

J'ai résolu le pb via de bon algorithmes mais voudrait implémenter une façon de trouver l'enveloppe la plus couteuse possible -> je détermine tous les polygones possibles à partir des points de mon polygone premier & test si ils sont convexes ou non. Or impossible de trouver une fonction récursive me permetant de trouver tous les sous ensembles & permutation d'une liste de n élèments (en l'occurence ma liste de point).
J'ai bien des idées de base mais rien n'aboutit.
Voilà, si jamais qqn a une petite idée en tête à me communiquer...
Coordialement,
LlufRuS

[Zavonen]

Il me semble avoir proposé une solution en Java dans la discussion de Malvina intitulée "determination des combinaisons".
J'ai depuis développé cette ébauche (composition, puissance, inverse, décomposition en cycles, signature...)

[LlufRuS]

Pas tout à fait, je ne souhaite pas avoir toutes les permutations de ma liste mais aussi les sous ensembles.
Exemple avec n=5
Je pourais en effet calculer toutes les permutations avec 5 elements
puis 4,puis 3 ...
mais pour diverses raisons, je ne souhaite pas faire ainsi (en parti car l'ensemble des permutations au delà de 14elements devient très longt & me bouffe la pile.)

Je voudrais travailler de la façon suivante : (en ramenant le pb à un arbre)
elem1 elem2 ..... elemN
Nelem-elem1 Nelem-elem2
Nelem-elemrang1-elemrang2 Nelem-elemrang1-elemrang2

Moué, pas très compréhensible mon truc la m'enfin la technique reviendrait a calculer la partie gauche de l'arbre, remonter, calculer la partie droite, ... afin de ne pas dépasser de pile.
(toujours pour 4 élèments, le début du résultat donnerait)
1
12
123
1234
124
1243
13
132
1324
134
1342 ...

Je prie d'excuser le peu de clarté émanant de mes explications pour toutes personnes lisant ce post.

[Graffito]

Bonjour,

Si n est le nombre de points du polygon initial, on peut directement déterminer les enveloppes de x points (x<n) en enlevant m points (m=n-x).
On peut éviter une procedure récursive en codant dynamiquement l'équvalent des m boucles imbriquées que l'on aurait statiquement codées ainsi :

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
   i0:=0
   for i1=i0+1 to n-m+1 do begin
        remove(i1) 
        for i2=i1+1 to n-m+2 do begin 
             remove(i2) 
             for i3=i2+1 to n-m+3 begin 
                  ...
                       for i<m>=i<m-1> to n begin
                            remove(i<m>)  
                            end               
                  ...    
             end
        end
 
    end

Pour cela on codera avec une boucle while unique et des tableaux pour les valeurs des indices de boucle.

[Zavonen]

Vous pouvez déjà récupérer la liste des sous-ensembles, par exemple avec un petit pgm comme ça c'est du Python mais vous pouvez le réécrire en n'importe quoi:

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
import copy
 
def subsets (L):
    if L==[]:
       return [[]]
    else:
        x=L[0]
        L.pop(0)
        S=subsets(L)
        T=[]
        for i in range(0,len(S)):
            V=copy.deepcopy(S[i])
            V.append(x)
            T.append(V)
            T.append(S[i])
    return T
 
 
print subsets ([1, 2])

puis ensuite pointer sur cette liste et utiliser une fonction comme 'permutations' de mon exemple (autre discussion) pour chaque élément de la liste, faire les traitements puis éventuellement nettoyer. De la sorte vous n'aller pas cumuler les appels récursifs et votre pile a des chances de ne pas exploser. Mais enfin, c'est vrai un SIMPLE APPEL à 'permutations' sur un ensemble à 14 éléments risque de consommer trop de ressources (pile et mémoire confondues) Il faudrait donc réécrire la fonction permutations pour qu'elle stocke le résultat dans un fichier sur disque. Cela dit, pour un ensemble à 14 éléments le nombre des parties étant de 16 K il y a peut être aussi intérêt à les stocker sur disque et à les appeler une par une.

[LlufRuS]

Bonjour,
en tout premier lieu merci de vos réponses.
La solution a en fait été simple : se reposer, passer une bonne nuit de sommeil & hop la solution est apparue au réveil... comme quoi savoir s'arreter peut parfois faire du bien.
Pas bien comprit a quoi m'aurait servi le fait de retirer des points à mon polygone mais peut importe; la façon dont je voulais créer mon arbre revenait simplement à prendre une permutation par ordre lexicographique & à en étudier les différents sous ensemble, puis la seconde permutations ...
Mon empilement récursif correspondant ainsi à mon nbr d'élement, ce nbr ne dépassant généralement pas la vingtaine, tout va bien.
En gros, un sujet sur ce forum pour rien.
Bonne continuation a tous,
LlufRuS