Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Décomposition "incomplète" sur une base n

Posté par
bebekija
05-03-09 à 13:20

Bonjour à tous,

Je suis bloqué depuis plusieurs jours sur un problème en apparence simple :

J'étudie des empilements de p couches, chaque couche étant choisie parmi n matériaux désignés par un indice allant de 0 à (n-1).

Il existe donc np empilements ordonnés différents.

Pour étudier successivement chacun de ces empilements, j'ai créé une boucle tournant sur un seul indice, mais qui permet de reconstituer l'empilement en décomposant cet indice sur la base n :

   Pour i de 0 à np - 1
           i = a1.np-1 + a2.np-2 + ... + ap-1.n1 + ap.n0

           empilement = [a1 a2 ... ap-1 ap]
           .
           ...
   Fin boucle

Jusque là tout va bien...

La ou ca se complique, c'est que l'ordre des couches n'a en fait aucune importance, et je cherche donc à restreindre la sélection des couches à celles qui constituent des combinaisons originales.

Exemple : pour un empilement de 3 couches à choisir parmi deux types possibles
Sélectionner uniquement [0 0 0]  ;  [0 0 1]  ;  [0 1 1]  ;  [1 1 1]
et laisser de coté [0 1 0]  ;  [1 0 0]  ;  [1 0 1]  et  [1 1 0] qui sont equivalentes à certaines ci-dessus.

Ceci est très simple à faire à la main (quoique rapidement très fastidieux)
Il n'est pas non plus très compliqué de faire cela par des boucles imbriquées.
En effet, si on reprend l'exemple ci-dessus, ca donne :
    Pour i1 allant de 0 à 1
         Pour i2 allant de i1 à 1
              Pour i3 allant de i2 à 1
                   empilement = [i1 i2 i3]
              Fin boucle
         Fin boucle
    Fin boucle

MAIS cela suppose que les p boucles soient écrites dans le code, ce qui n'est pas très pratique, puisqu'il faudrait un fichier source par valeur de p, et en plus comme mes empilements peuvent facilement aller jusqu'à 20 ou 24 couches, je me vois mal écrire 20 boucles imbriquées...


DONC : je cherche des bonnes ames qui auraient une lumineuse idée pour pouvoir faire cette sélection en utilisant une programmation "générale", comme celle que j'ai utilisée dans le premier exemple ou je ne fais aucune différenciation (d'où la décomposition "incomplète" du titre).
Personnellement, je n'ai plus d'idées, et je suis meme en train de me demander si la solution à mon problème existe réellement.


D'avance merci à ceux qui auront eu le courage de lire ca jusqu'au bout.

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !