Discussion :

[Amiral56]

Bonjour ,
Cela fait quelques jours que je travaille sur le problème suivant :
J'ai plusieurs cellules dans chaque cellule il y a quatre places , chaque place peut être soit vide soit contenant un carton. L'ensemble de mes cartons sont numérotés de 1 à n et dispatchés dans le désordre dans ces différentes cellules.
L'objet de l'exercice est de trouver une méthode permettant d'utiliser les places vides afin de réarranger tous les cartons pour pouvoir les sortir de le bon ordre ( 1-2....n).
NB : Si une cellule est pleine on peut pas accéder au carton qui est dans le fond, pour accéder à ce carton là il faudra déplacer les trois autres.

J'ai essayé dans un premier temps de réduire mon exercice. J'ai considérer que j'ai 8 cartons numérotés de 1 à 8 et répartis aléatoirement sur les 4 cellules (4*4 places). Mais il m'est toujours difficile de poser le problème mathématiquement.
Je suis ouvert à toutes propositions. Je vous remercie par avance.
(Ci joint un document permettant de mieux visualiser le problème)

[Golgotha]

Bonjour,

Rapidement, ça ressemble au problème des tours de Hanoï, as tu regardé de ce coté là si il n'y avait pas des solutions qui conviennent à ton problème ?

[Amiral56]

Bonjour Golgotha,

Je tiens à vous remercier de votre retour.
Je vais y jeter un coup d’œil, à première vue c'est exactement le même problème. Je vous tiendrai informé.

Merci infiniment.

[Amiral56]

J'ai regardé le problème des Tours de Haroi. Mais ce n'est pas tout à fait mon problème l'objectif est le même certes la seule différence c'est que dans les Tours de Haroi à l'état initial on a une cellule de cartons déjà rangée de 1 à 8 sauf qu'en réalité c'est pas le cas.
Voici un exemple :
------------------------------------------------
* A l'instant t0, j'ai ceci :
Celulle 1 : 1,9,0,0
Celulle 2 : 2,6,3,0
Celulle 3 : 4,5,8,7
Celulle 4 : 0,0,0,0

* Trouver un algorithme afin d'obtenir :
Celulle 1 : 4,3,2,1
Celulle 2 : 8,7,6,5
Celulle 3 : 0,0,0,0
Celulle 4 : 0,0,0,0
ou bien
Celulle 1 : 7,6,3,1
Celulle 2 : 8,5,4,2
Celulle 3 : 0,0,0,0
Celulle 4 : 0,0,0,0
etc ... ( L'objectif ça serait de pouvoir sortir tous les cartons dans l'ordre).
------------------------------------------------------

Contrairement à Tours de Haroi :
Initialement on a :
Celulle 1 : 4,3,2,1
Celulle 2 : 0,0,0,0
Celulle 3 : 0,0,0,0

Après le calcul on obtient :
Celulle 1 : 0,0,0,0
Celulle 2 : 0,0,0,0
Celulle 3 : 4,3,2,1

-------------------------------------

Je vous remercie !

[Celelibi]

Si tu as k places par cellule et moins de k places libre au total, tu n'es pas sûr qu'il existe une solution.
Par exemple, si tu as :
(1, 2, 3, 4)
(5, _, _, _)
Tu ne peux rien faire.

S'il existe k places libres (ou plus), alors la solution est triviale puisque tu peux aller chercher le carton que tu veux, et le placer où tu veux (il me semble).

Si j'ai bien compris, ton objectif n'est pas forcément de les ordonner de manière stricte, mais juste t'assurer que les cartons "plus au fond" ont un numéro plus grand que ceux "devant".

Autrement dit, pour une cellule (a1, a2, a3, a4) tu veux que a1 <= a2 <= a3 <= a4 (avec pas de carton = +inf pour simplifier).

Est-ce que tu veux minimiser le déplacement des cartons ?

Si tu veux poser le problème de façon mathématique, tu peux dire que tu as des k-uplets qui contiennent soient un entier soit un élément ⊥ (pas de carton) et définir l'opération de déplacement d'un carton. Mais je ne suis pas sûr que ça aide.

[Amiral56]

Celelibi,
Je tiens à vous remercie de votre retour.
L'objectif est de ranger les cartons de telle sorte de pouvoir les sortir dans l'ordre et aussi de minimiser le déplacement des cartons.
Alors existerai t il une fonction à minimiser ça risquerait d'être difficile de la trouver !
Une précision vous aviez dit que la solution était triviale. Certes pour l'exemple que j'ai cité mais en réalité j'aurai affaire à une centaine de cellules contenant des cartons que je dois ranger. Cela devient vite complexe .

Je vous remercie !