Discussion :

[Pedro4]

Bonjour,

je cherche un algorithme me permettant de résoudre le problème de numérotation suivant:

J'ai un ensemble composé de sous-ensembles et de composants.
Un conteneur peut être constitué d’un jeu de sous-ensembles et de composants.
Je dois pouvoir numéroter le conteneur, ainsi que les composants.

La numérotation peut être effectuée suivant le principe suivant : numero/partie

Numero et partie sont des entiers positifs.

On peut affecter une fourchette de numéros à un ensemble ou à un sous-ensemble.
Un numéro peut avoir de 1 à n parties.
Une fourchette commence a un minimum et un maximum.
On a un jeu illimité de fourchettes.

Ainsi on pourrait affecter une fourchette à un ensemble, et des sous-fourchettes aux sous-ensembles (ou des fourchettes différentes). Les ensembles/sous-ensembles sont constitués de composants. On peut assigner une partie à un composant, dans la limite des parties autorisées pour un numéro. Cette limite est égale à n. Ensuite on utilise un autre numéro pour le sous-ensemble. Ainsi un sous-ensemble peut correspondre à plusieurs numéros.

Cela est simple pour le moment.

Le véritable problème vient lorsque l’on constitue les conteneurs. Ces conteneurs sont constitués de composants venant d’ensembles divers.

On doit assigner un numéro/partie à un container.
Le problème est que je dois conserver une numérotation cohérente avec les numérotations des divers composants.
On peut numéroter un composant seul ou bien à l’intérieur de divers conteneurs.
Lorsqu’un composant a été numéroté une fois, il conserve à vie le même numéro/partie.

Je vois ici diverses possibiltés :
- conserver un jeu de numérotation spécifique pour les conteneurs, qui ne prendrait pas en compte les numéros/parties de chacun des composants.
- ne pas utiliser de conteneurs. Mais ceci est exclu.
- avoir une numérotation plus flexible permettant de lier les numéros d’un conteneur aux numéros de ses composants, sachant qu’un composant peut faire partie de plusieurs conteneurs.

Existe-t-il des algorithmes pour cela ?

Mon problème peut être vu comme lié à la numérotation de répertoires et de fichiers. Les fichiers peuvent être exportés de n’importe quel répertoire et incorporé dans un fichier zip.
Il faut trouver un algorithme permettant de numéroter les fichiers et les conteneurs zip de manière à ce que ce soit cohérent avec les répertoires.

[pseudocode]

Mis à part le fait que je n'ai pas tout compris au problème, je tique sur ce passage :

"Le problème est que je dois conserver une numérotation cohérente avec les numérotations des divers composants"

Que veux dire "cohérente" dans ce contexte ?

[prgasp77]

Bonjour,
je m'excuse mais j'ai du mal à saisir le problème, tu passes trop vite sur celui-ci pour t'étaler sur les solutions envisageables.
Il y a un conteneur, un ensemble E, des sous-ensembles et des composants. Mais on en sait pas beaucoup plus :

• Il semble que ton conteneur soit une partie de E. Peut-il y avoir des doublons ? Y a-t-il un ordre ?
• E contient à la fois des sous-ensembles et des composants. Mais que contiennent les sous-ensembles ?
• Que faut-il numéroter exactement ?

Cdlt,

[Pedro4]

Merci pour vos questions.

Que veux dire "cohérente" dans ce contexte ?

C'est une réponse que je dois apporter.
En fait, il serait souhaitable de réutiliser les numéros des composants pour identifier un conteneur. Étant donné qu'il y a un seul numéro/partie par conteneur, et qu'il y a plusieurs composants avec chacun son numéro/partie, cela me semble impossible.
Par contre on pourrait réutiliser le numéro/partie d'un conteneur pour déterminer le numéro/partie de chacun des composants.
Mais comme chacun des composants peut faire partie de plusieurs conteneurs, cela semble également difficile.
Alors peut-être faudrait-il utiliser une numérotation différente pour les conteneurs et les composants?

# Il semble que ton conteneur soit une partie de E. Peut-il y avoir des doublons ? Y a-t-il un ordre ?

Effectivement chaque conteneur est une sous-partie de E.
E peut être décomposer en sous-ensembles E1, E2, E3... et chaque sous-ensemble peut également être décomposé. Par exemple E1 en E1.1, E1.2 etc.
Il ne peut pas y avoir de doublons.
Je ne peux pas utiliser une numérotation du type 1.1, 1.1.1 etc mais je suis obligé de passer par une numérotation du type numéro/partie, où chaque numéro provient d'une fourchette. Les fourchettes disponibles correspond à l'ensemble des entiers naturels positifs.
Chaque numéro est constitué d'une nombre de parties limité. Donc un numéro est constitué de 0 à n parties.
Par contre un ensemble peut être constitué d'un nombre d'éléments fini mais supérieur à n.

# E contient à la fois des sous-ensembles et des composants. Mais que contiennent les sous-ensembles ?

Les sous-ensembles contiennent également des sous-ensemble et des composants.
C'est exactement comme dans un système d'exploitation où un répertoire (l'ensemble), peut contenir des fichiers et des sous-répertoires. Et ces sous-répertoires contiennent également des répertoires et des fichiers.

# Que faut-il numéroter exactement ?

Les composants.
Les conteneurs contenant un sous-ensemble d'éléments.
Il ne faut pas numéroter les ensembles.
Par analogie avec le système d'exploitation: il faudrait numéroter les fichiers ET des ZIP contenant un ensemble de fichiers provenant de n'importe quel répertoire.

Une idée serait d'assigner une fourchette à un répertoire.
Mais comment faire lorsque le numéro maximal de la fourchette est atteint? On assignerait une fourchette supplémentaire (avec un jeu de numéro pas forcément consécutif).
Ce que je ne trouve pas: comment numéroter les conteneurs en utilisant les numéros de répertoire?
Peut-être n'y a-t-il pas de solution? Alors on pourrait dire qu'un conteneur ne contiendrait que des éléments provenant d'un répertoire particulier.
Si un conteneur contient des éléments provenant de répertoires différents alors on décompose le conteneur en plusieurs conteneurs par répertoire, pour que chacun ait un numéro correct.
Mais dans ces conditions, si chaque élément extrait provient d'un répertoire différent, on se retrouve avec un jeu de conteneurs contenant chacun un seul élément. Ce qui me semble remettre en cause le concept de conteneur.
Dans ces conditions peut-être un autre concept serait plus adapté? Je ne pense pas à un concept du type "groupe" qui serait en fait la même chose que le conteneur.

En fait, j'ai toute la flexibilité voulue, sauf que je dois utiliser ce concept de numéro/partie pour rester cohérent avec un système cible.
Le système cible doit pouvoir comprendre, à partie des numéros/parties reçus, de quel ensemble source proviennent les éléments.
Ce dernier point me semble aussi compliqué, voire impossible. Néanmoins je dois prouver pourquoi, et proposer des alternatives.

D'où ma question sur les algorithmes existants...
En fait, il me semble que la complexité vient du fait que l'on cherche à avoir deux types de numérotation incompatibles.
D'où ma question relative aux deux systèmes de numérotation non liés: un pour les conteneurs, un pour les composants.
Mais l'incompatibilité est-elle réelle?

[Nemerle]

Peux-tu donner juste un exemple simple ensembles/composants/numérotation?

[Pedro4]

Peux-tu donner juste un exemple simple ensembles/composants/numérotation?

Je prépare un tableau avec un exemple.
En fait, j'aurais dû commencer par cela, c'est beaucoup plus explicite.
Merci!
ps: je poste le tableau dès qu'il est prêt.

[Pedro4]

Je mets trois pièces jointes.
La première donne une liste de fourchette.
Une fourchette est définie par un numéro min, un numéro max, et un nombre de partie autorisée par numéro.
Dans un ensemble, un composant peut avoir déjà reçu un numéro ou pas.
La pièce jointe numérotationDeComposants montre une liste de composants déjà numérotés.
Un ensemble a une ou plusieurs séquences qui lui sont affectées.
Quand on numérote, on commence par utiliser la première séquence auquel cet ensemble a droit.
Dans la séquence on commence par le premier numéro.
Par numéro, on commence par la première partie.
Quand on a atteint le nombre maximum de parties autorisées on change de numéro.
Quand on a atteint le nombre maximum de numéros autorisés on change de séquence.
On peut avoir un nombre illimité de séquence par ensemble.

La troisième figure numérotationDeConteneurs montre comment est constitué un conteneur.
Il peut avoir des composants venants d'ensemble différents et chaque composant a déjà été numéroté ou pas.
Ce que je cherche c'est à numéroter le plus efficacement possible les conteneurs, en utilisant également un système de fourchette/numéro/partie.
De même ces conteneurs ayant été numérotés, je cherche à trouver comment numéroter (par la suite? en même temps?) le plus efficacement possible les composants qui ne sont pas encore numérotés à l'intérieur d'un conteneur.
Une fois qu'un composant/conteneur a reçu un numéro/partie, il ne peut plus en changer.

[prgasp77]

Je comprends pas bien cette histoire d'identification numéro/partie ... qu'en est-il quand on a une arborescence profonde ?

Je propose de parcourir l'arbre en largeur et de numéroter tout simplement les éléments (nom utilisé pour décrire les composants comme les conteneurs) par leur ordre de découverte. Afin de pouvoir retrouver le père d'un élément via son id, on peut utiliser un subterfuge : lorsque l'on descend d'un étage dans notre parcourt, on incrémente notre compteur de deux et non d'un. Ainsi, le père de l'élément d'id e est l'élément de plus grand id p tel que p < e et p+1 n'existe pas.

À vous Cognacq-Jay !