Permutations et combinaisons

GW-Basic, utilisé par PC-Basic

Programme avec Texte Seulement

PC-BASIC

Lorsque vous disposez des personnes (ou des objets) dans une ligne, l'ordre des arrangements est important. C'est ce qu'on appelle une permutation.

Considérez une file d'attente de cinq personnes au poste de police : de combien de manières une telle file d'attente peut-elle être permutée ?

Eh bien, n'importe lequel des cinq criminels présumés peut être placé dans la case la plus à gauche; puis, il en reste quatre pour la case à côté de lui; puis, trois personnes; puis, deux; et, enfin, une personne reste pour le placement final. Cela nous donne 5!, ou cent vingt, façons d'aligner cinq mécontents à la gare.

Au contraire, l'ordre des arrangements n'a souvent pas d'importance. C'est ce qu'on appelle une combinaison.

Supposons qu'au travail, vous ayez besoin d'un comité de cinq personnes sur les vingt-cinq personnes de votre service. Ici, peu importe l'ordre dans lequel vous choisissez les cinq personnes ; il importe seulement qu'un sous-ensemble unique de cinq personnes soit sélectionné. Nous utiliserons toujours des factorielles pour calculer la réponse, mais le calcul est un peu différent :

Il y a donc 53 130 sous-ensembles uniques de cinq personnes sur un ensemble de vingt-cinq.

Comme point de contraste, prétendez plutôt que l'ordre de sélection de cinq personnes (sur vingt-cinq) avait en fait de l'importance. On trouverait qu'il y a:

façons de permuter cet arrangement - beaucoup plus de façons qu'une combinaison de cinq personnes prises sur vingt-cinq.

PERCOMB.BAS peut calculer rapidement les permutations et les combinaisons, uniquement après avoir posé à l'utilisateur quelques questions simples.

Les boucles FOR/NEXT dominent la journée ici; ils sont nécessaires pour les calculs factoriels intermédiaires. La variable TEMP est utilisée à plusieurs reprises comme espace réservé.

Bien que le programme fonctionne aussi rapidement que possible, le code lui-même pourrait être écrit plus efficacement, plus proprement. Peut-être que l'algorithme factoriel, au lieu d'être codé à plusieurs reprises, pourrait plutôt être entré une fois en tant que sous-programme et appelé plusieurs fois. D'autres améliorations similaires sont sûrement possibles.

5 TEMP=1 'Définit la valeur de TEMP à un
18 KEY OFF:SCREEN 9:COLOR 15,1:CLS
20 PRINT "PERMUTATIONS VS COMBINAISONS"
30 PRINT:INPUT "Permutation (tapez 1) ou Combinaison (tapez 2) ou Quitter (tapez 3)";T
40 IF T=1 THEN GOTO 70
50 IF T=2 THEN GOTO 270
55 IF T=3 THEN CLS:END
60 GOTO 30
70 PRINT:PRINT "Perrautations : l'ordre d'arrangement compte."
80 INPUT "Combien y a-t-il d'articles / de personnes au total";TOTAL
85 TOTA=INT(TOTAL) 'S'assurer que la variable TOTAL est un entier
90 INPUT "Combien, sur le total, souhaitez-vous les disposer en ligne";SUBSET
95 SUBSET=INT(SUBSET) 'S'assurer que la variable SUBSET est un entier
100 FOR LOOP1=1 TO TOTAL
110 TEMP=TEMP*LOOP1 'Calcule la factorielle: LOOP1
120 NEXT LOOP1
130 NUMER=TEMP 'Définit le numérateur sur la factorielle LOOP!
135 TEMP=1 'Réinitialise la valeur de TEMP à un
140 FOR LOOP2=1 TO (TOTAL-SUBSET)
150 TEMP=TEMP*LOOP2 'Calcule la factorielle:SUBSET!
160 NEXT LOOP2
170 DENOM=TEMP 'Définit le dénominateur sur la factorielle SUBSET!
175 TEMP=1 'Réinitialise la valeur de TEMP à un
180 PRINT
185 PRINT "Le nombre de façons d'organiser ces éléments est: ";NUMER/DENOM
190 GOTO 30
270 PRINT:PRINT "Combinaisons : l'ordre d'arrangement n'a pas d'importance."
280 INPUT "Combien y a-t-il d'articles / de personnes au total";TOTAL
285 TOTAL=INT(TOTAL) 'S'assurer que la variable TOTAL est un entier
290 INPUT "Quel est le sous-ensemble du total que vous souhaitez trouver";SUBSET
295 SUBSET=INT(SUBSET) 'S'assurer que la variable SUBSET est un entier
300 FOR LOOP1=1 TO TOTAL
310 TEMP=TEMP*LOOP1 'Calcule la factorielle: LOOP!
320 NEXT LOOP1
330 NUMER=TEMP 'Définit le numérateur sur la factorielle LOOP!
335 TEMP=1 'Réinitialise la valeur de TEMP à un
340 FOR LOOP2=1 TO SUBSET
350 TEMP=TEMP*LOOP2 'Calcule la factorielle:SUBSET!
360 NEXT LOOP2
370 DENOM1=TEMP 'Définit la première partie du dénominateur sur la factorielle SUBSET!
375 TEMP=1 'Réinitialise la valeur de TEMP à un
380 FOR LOOP3=1 TO (TOTAL-SUBSET)
390 TEMP=TEMP*LOOP3 'Calcule la factorielle: (TOTAL-SUBSET)!
400 NEXT LOOP3
410 DENOM2=TEMP 'Définit la première partie du dénominateur sur la factorielle SUBSET!
415 TEMP=1 'Réinitialise la valeur de TEMP à un
430 PRINT
435 PRINT "Le nombre de façons d'organiser ces éléments est: ";NUMER/(DENOM1*DENOM2)
440 GOTO 30