Algorithme de permutation de Heap
GW-Basic, utilisé par PC-Basic
Programme avec Texte Seulement
Produire un algorithme pour permuter n objets est une proposition changeante ; la plupart de ces algorithmes échangent à plusieurs reprises des éléments, d'une manière méthodique, pour énumérer complètement toutes les permutations. Mais il est difficile d'être à la fois (1) exhaustif avec l'énumération et (2) de ne répéter aucune permutation.
Le mathématicien B. R. Heap, au début des années 1960, a écrit un algorithme systématique qui satisfait les deux conditions. Voici comment il l'a expliqué :
Envisager une méthode inductive pour les permutations de n objets.
Supposons que l'on puisse trouver une liste d'échanges qui permute (n — 1) objets.
Si nous fixons maintenant l'objet dans la nième cellule, nous pouvons permuter les premiers (n — 1) objets parmi les (n — 1) premières cellules.
Maintenant, échangez le nième objet avec l'un des premiers (n - 1) objets et permutez à nouveau les premiers (n - 1) objets.
Échangez à nouveau le nième objet avec l'un des premiers (n - 1) objets, en vous assurant que cet objet n'a pas précédemment occupé la nième cellule.
Répétez maintenant le processus jusqu'à ce que chacun des objets ait rempli la nième position tandis que l'autre (n - 1) a été permuté, et clairement toutes les n! permutations ont été trouvées.
Extrait de l'article intitulé "Permutations par échanges".
Un tel processus d'échanges pour arriver aux n! permutations est maintenant formellement appelé l'algorithme de Heap.
Le point d'exclamation (!) fait référence aux factorielles, une notion mathématique conçue pour raccourcir certains problèmes de comptage. Par exemple, 3! = 3x2x1 = 6, 6! = 6x5x4x3x2x1 = 720, etc. Par définition, 0! = 1.
En gros, voici comment cela fonctionne : démarrer un compteur I à zéro ; créez un tableau A d'éléments que vous souhaitez permuter.
Effectuez les étapes suivantes (n — 1) fois (où n représente le nombre total d'éléments), en incrémentant le compteur I de 1 à chaque fois :
• Si n est impair, permuter les
éléments de A indexés 1 et n ;
• Si n est pair, intervertir les éléments de A
indexés I et n ;
• Continuez à appliquer l'algorithme ci-dessus jusqu'à ce
que toutes les permutations aient été générées.
HEAP.BAS, détaillé ci-dessous, traduit l'algorithme de Heap en GW-BASIC.
Notez que l'échange d'éléments dans les tableaux est effectué par des variables TEMP utilisées à plusieurs reprises (bien que nous aurions pu utiliser des instructions SWAP).
Une boucle WHILE...WEND continue l'itération de l'algorithme jusqu'à ce que tous les ensembles de permutations aient été produits.
Et, enfin, un ensemble de sous-programmes, y compris un sous-programme qui appelle un autre sous-programme, aide à garder les choses organisées.
L'utilisation de l'algorithme de Heap est probablement le moyen le plus efficace de permuter n objets, mais il existe d'autres algorithmes possibles. N'hésitez pas à créer le vôtre.
Cependant, sachez que la plupart des implémentations de l'algorithme de Heap sont de type récursif, mais HEAP.BAS est non récursif. Un algorithme récursif est-il même possible dans GW-BASIC ?
Pour le savoir, lisez la section Récursivité.
5 REM HEAP.BAS
10 KEY
OFF:CLS
15 COUNTER1=0
17 COUNTER2=0
20 INPUT "Permutations : Combien d'éléments";N
30 DIM C(N)
35 DIM A(N)
40 FOR X=1 TO N-1
50 A(X)=X
60 NEXT X
65
GOSUB 3000 'Sortie du tableau d'origine
70 I=0
80 WHILE I<N
90 IF
C(I)<I THEN GOSUB 1000 ELSE GOSUB 2000
100 WEND
110 PRINT "Il y a
";COUNTER2;" permutations de ";N;" élements."
120 END
1000
'Sous-programme pour
1010 'Déterminer si pair ou impair
1020 B=I MOD 2
1030 IF B=0 THEN TEMP=A(O):A(0)=A(I):A(I)=TEMP
1040 IF B=1 THEN
TEMP=A(C(I)):A(C(I))=A(I):A(I)=TEMP
1050 GOSUB 3000
1060 C(I)=C(I)+1
1070 I=0
1100 RETURN
2000 C(I)=0
2010 I=I+1
2020 RETURN
3000
'Sous-programme pour sortir le tableau 'A'
3005
COUNTER1=COUNTER1+1:COUNTER2=COUNTER2+1
3006 IF COUNTER1>22 THEN INPUT
"Appuyez <ENTER> pour la prochaine série...";ENT$:COUNTER1=0
3010 FOR Y=0 TO
N-1
3020 PRINT A(Y);" ";
3030 NEXT Y
3040 PRINT
3050 RETURN
