Permutations sur la calculatrice TI-82

Publié le Mis à jour le

En ce moment, je suis entrain d’écrire un livre sur la programmation sur la calculatrice TI-82 (de Texas Instruments). Je me suis demandé si on pouvait programmer des permutations de nombres entiers (de 1 à n) ou réarranger aléatoirement une liste.

1) Permutations

Soit n un entier naturel. On note \mathbb{N}_n = \{1,2,\ldots,n\}.

DÉFINITION. On appelle permutations à n élements, toute bijection \sigma : \mathbb{N}_n \to \mathbb{N}_n, c’est-à-dire que tout élément de \mathbb{N}_n est image d’exactement un élément de \mathbb{N}_n.

EXEMPLE. \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4\end{pmatrix} est une permutation de \mathbb{N}_5. Si \sigma est cette permutation alors \sigma(1) = 2, \sigma(2) = 3, \sigma(3) = 1, \sigma(4) = 5 et \sigma(5) = 4. On peut noter cette permutation \sigma = (123)(45).

2) Ébauche du programme PERMU

On se donne une liste L_1 de n éléments ordonnées 1 à n (c’est-à-dire que pour tout 1 \le k \le n, L_1(k) = k. On sélectionne un entier au hasard de 1 à n (disons p), on associe L_1(p) au premier élément de la liste L_2 ainsi L_2(1) = L_1(p) et on supprime le p-ième élément de la liste L_1. Pour le deuxième élément de la liste L_2, on sélectionne un entier au hasard de 1 à n-1 (disons k), on associe L_1(k) au deuxième élément de la liste L_2 tel que L_2(2) = L_1(k) et on supprime le k-ième élément de la liste L_1 et ainsi de suite, jusque tant qu’il n’y a plus d’élément dans la liste L_1 (après n itérations).

3) Génération de la liste L_1

Très simple ! On demande à l’utilisateur d’entrer un entier n et pour k entre 1 à n, on associe L_1(k) := k. Cela donne en langage TI-BASIC.

PROGRAM:PERMU
:EffListe L1
:Prompt N
:For(K,1,N)
:K->L1(K)
:End
:Disp L1

4.1) Effacer un élément de la liste

On génère une liste L_1 comme dans la section 3 et on veut effacer le t-ième élément de la liste L_1 (avec 1 \le t \le n). Pour cela, on affecte tous les éléments L_1(k-1) := L(k) (pour tout t+1 \le k \le n) et on réduit la dimension de la liste L_1 pour supprimer le dernier élément de la liste.

PROGRAM:PERMU
:EffListe L1
:Prompt N
:For(K,1,N)
:K->L1(K)
:End
:Prompt T
:For(K,T+1,N)
:L1(K-1)->L1(K)
:End
:dim(L1)-1->dim(L1)

4.2) Effacer toute la liste

Si on veut supprimer tour à tour (et aléatoirement) tous les éléments de la liste, on peut s’inspirer de ce qui a été fait en 4.1 en ajoutant une boucle TantQue sur la dimension de la liste L_1.

PROGRAM:PERMU
:EffListe L1
:Prompt N
:For(K,1,N)
:K->L1(K)
:End
:While dim(L1)>1
:entAléat(1,dim(L1))->T
:For(K,T+1,dim(L1))
:L1(K-1)->L1(K)
:End
:dim(L1)-1->dim(L1)
:Disp L1
:End
:dim(L1)-1->dim(L1)

5) Le cœur du programme

Voici le programme PERMU qui réordonne aléatoirement les éléments d’une liste L_1 = \{1,...,n\} en une nouvelle liste L_2.

PROGRAM:PERMU
:EffListe L1,L2
:Prompt N
:For(K,1,N)
:K->L1(K)
:End
:0->C
:While dim(L1)<>0
:entAléat(1,dim(L1))->T
:C+1->C
:L1(T)->L2(C)
:For(K,T+1,dim(L1))
:L1(K)->L1(K-1)
:End
:dim(L1)-1->dim(L1)
:End
:L1(1)->L2(C+1)
:Disp L2

6) Pour aller plus loin

On peut utiliser ce programme pour réordonner aléatoire une liste quelconque de nombres, il suffit de reprogrammer la génération de la liste L_1 et appliquer le même principe pour le réagencement.

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s