Affichage des combinaisons

Affichage combinaisons

GW-Basic, utilisé par PC-Basic

Si les mathématiques et la langue anglaise s'accordaient parfaitement, une serrure à combinaison serait appelée une serrure à permutation.

Voici pourquoi : avec les permutations mathématiques, l'ordre des arrangements est important.

Si vous savez que la combinaison d'une serrure à combinaison est 23-54-17, vous ne vous attendez pas à ouvrir la serrure avec 54-17-23 ou 17-54-23 - il n'y a qu'un seul ordre correct pour déverrouiller la serrure.

Avec les combinaisons mathématiques, cependant, l'ordre des arrangements ne fait aucune différence - seuls les éléments particuliers du sous-ensemble.

Si la combinaison correcte d'une serrure à combinaison est 23-54-17, alors n'importe laquelle de ces permutations, où l'ordre compte, ouvrira la serrure :

23-54-17
23-17-54
17-23-54
17-54-23
54-17-23
54-23-17

Ces six permutations ne représentent qu'une seule combinaison, puisque chaque combinaison doit contenir un sous-ensemble unique d'éléments.

Voici un exemple différent, plus abstrait. Supposons que nous considérons toutes les combinaisons possibles de trois lettres parmi un ensemble de cinq lettres : A, B, C, D et E. Les combinaisons possibles sont :

ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE

Ainsi, il existe dix sous-ensembles uniques de trois éléments tirés de cinq éléments. Avant de continuer, regardez attentivement la manière systématique dont les combinaisons sont établies ci-dessus ; c'est ainsi que CHOOSE.BAS, illustré ci-dessous, énumérera également les ensembles.

En utilisant un coefficient binomial, nous pouvons démontrer qu'il existe en effet précisément dix sous-ensembles uniques :

Les nombres 5 et 3 entre parenthèses sont le coefficient binomial, et il se lit comme "5 choisit 3".

Au lieu d'utiliser plusieurs noms de variables, plusieurs tableaux, chacun déclaré avec une instruction DIM, sont utilisés dans le programme pour permettre l'indexation des données.

Plus précisément, le tableau ARRAYELEMENTS contiendra un ensemble de nombres naturels (c'est-à-dire 1, 2, 3, ...).

Ces nombres naturels seront réorganisés pour faire la liste de toutes les combinaisons possibles d'éléments, servant éventuellement d'indices pour les valeurs du tableau SETOFELEMENTS$.

À partir de la ligne 210, une boucle WHILE-WEND répétera le code jusqu'à ce qu'une règle d'arrêt, définie pour être égale à une certaine somme, soit satisfaite.

Ensuite, après que le kème élément d'un tableau a été incrémenté d'une unité, plusieurs boucles FOR/NEXT et un certain nombre d'instructions conditionnelles vérifient si d'autres éléments doivent également être incrémentés.

Enfin, une fois la dernière combinaison imprimée à l'écran, le nombre total de combinaisons (c'est-à-dire la valeur du coefficient binomial de n choisir k) est relayé.

Aussi difficile que CHOOSE.BAS est à décoder, un programme analogue qui énumère toutes les permutations possibles serait encore plus difficile à écrire.

Donc, si vous recherchez un défi GW-BASIC important, ne cherchez pas plus loin ; c'est une serrure. (Ou regardez simplement HEAP.BAS, présenté dans la section suivante.)

1 REM CHOOSE.BAS
5 DIM SETOFELEMENTS$(15)
6 DIM ARRAYELEMENTS(15)
7 C0MBINATI0NNUMBER=1
10 KEY OFF
20 CLS
30 INPUT "Combien d'items au total (max = 15)";N
40 IF N>15 THEN N=15
50 IF N<1 THEN N=1
60 INPUT "Choisissez combien parmi ces éléments totaux (max=15)";K
70 IF K>15 THEN K=15
80 IF K<1 THEN K=1
85 'Une boucle FOR/NEXT pour capturer tous les éléments
90 PRINT "Entrez votre ";N;" items, appuyez <ENTER> après chaque:"
100 FOR LOOP=1 TO N
110 INPUT SETOFELEMENTS$(LOOP)
120 NEXT LOOP
130 'Une boucle FOR/NEXT pour créer des numéros d'index
140 FOR X=1 TO K
150 ARRAYELEMENTS(X)=X
160 NEXT X
170 'Find the maximum sum (for stopping rule)
180 FOR A=N TO (N-K+1) STEP -1
190 MAXSUM=MAXSUM+A
200 NEXT A
210 WHILE CHECKSUM < (MAXSUM+1)
220 CHECKSUM=0
230 COUNTER=0
240 CURRENTELEMENT=0
245 'Imprimer l'élément
250 FOR START=1 TO K
260 IF START=1 THEN PRINT:PRINT "COMBO #:";COMBINATIONNUMBER;": ";SETOFELEMENTS$ (ARRAYELEMENTS(START));
270 IF START>1 THEN PRINT " ";SETOFELEMENTS$(ARRAYELEMENTS(START));
275 NEXT START
277 PRINT:INPUT "Appuyez <ENTER> pour voir la combinaison suivante...";A$
280 ARRAYELEMENTS(K)=ARRAYELEMENTS(K)+1
290 FOR Y=K TO 2 STEP -1
300 IF ARRAYELEMENTS(Y)>(N-COUNTER) THEN GOSUB 500
310 COUNTER=COUNTER+1
320 NEXT Y
330 FOR T=1 TO K
340 CHECKSUM=CHECKSUM+ARRAYELEMENTS(T)
350 NEXT T
360 COMBINATIONNUMBER=COMBINATIONNUMBER+1
370 WEND
380 IF COMBINATIONNUMBER-1=1 THEN PRINT "Il y a ";COMBINATIONNUMBER-1;" combination."
390 IF COMBINATIONNUMBER-1>1 THEN PRINT "Il y a ";COMBINATIONNUMBER-1;" combinations."
400 END
500 ARRAYELEMENTS(Y-1)=ARRAYELEMENTS(Y-1)+1
510 CURRENTELEMENT=Y
520 FOR R=CURRENTELEMENT TO K
530 ARRAYELEMENTS(R)=ARRAYELEMENTS(R-1)+1
540 NEXT R
550 RETURN

Recherche personnalisée