mardi 20 juillet 2021

Eviter les boucles imbriquées

Nous utilisons fréquemment des boucles for imbriquées. Il arrive que la profondeur de ces imbrications soit trop grande (ou qu'elle soit variable) pour pouvoir les écrire en dur. Ici je donne ma solution en C et en python.

Exemple simple

Il s'agit ici d'afficher (et accessoirement dénombrer) les tirages de p numéros parmi n sans remise et en tenant compte de l'ordre. Pour p raisonnable on écrira un code qui ressemble à :

for(int i=0; i<n; i++)
	for(int j=0; j<n; i++)
		for(int k=0; k<n; k++)
			...

Mais si p dépasse 3 ou 4, ça devient lassant. Pire, si p n'est défini qu'à l'exécution ça devient impossible, à moins d'utiliser des tableaux de variables d'indice dans les boucles for. C'est ce que je propose ici.

/* ex1.c.c
:w | !gcc % -o .%<
./.%<
*/
#include <stdio.h>
#include <stdlib.h>
/*
Tirage de p nombres parmi {0, 1, ... , n - 1} avec remise
Affiche tous les tirages
Exemple pour p = 3 et n = 5 affiche  
	(0, 0, 0) (0, 0, 1) (0, 0, 2) (0, 0, 3) ... (4, 4, 3) (4, 4, 4)
Retourne le nombre de tirages : n^p
Remplace :
for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
        for(int k=0; k<n; k++)
            ...
                ...
avec p boucles for
*/
int ex1(int p, int n);
void print(int p, int *v);
  
int main(int argc, char *argv[]) 
{
    printf("Tirages de p nombres parmi n AVEC remise\n");
    int p = 3, n = 5, c; // exemple
    printf("p = %d, n = %d\n", p, n);
    c = ex1(p, n); // nombre de tireages et affichage
    printf("\nNombre de tirages (%d^%d): %d\n", n, p, c);
}
 
void
print(int p, int *v)
{
	// affiche un t-uple v sous la forme (v0, v1, ... , vp)
	printf("(");
	for(int i = 0; i < p - 1; i++) printf("%d, ", v[i]);
	printf("%d) ", v[p - 1]);
}
 
int 
ex1(int p, int n)
{
    int c = 0, i; // c: compteur, i varable de boucle
    int v[p]; // v est une liste de p nombres 0, 1, ... , p
    for(i = 0; i < p; i++) v[i] = 0; // initialisation de v à 0
    // on quitte dès que le premier terme de la liste dépasse n - 1
    while(v[0] < n) { 
        c++; // compteur
		print(p, v);
        v[p - 1]++; // on incrémente le dernier terme
        for(i = p - 1; i > 0; i--) // propagation du dépassemnt éventuel
            if(v[i] == n) { // dépassement
                v[i] = 0; // remise à zéro
                v[i - 1]++; // propagation
            }
    }
    return c; // nombre de tirages
}

Le code est abondamment commenté. Le code source est là ex1.c.

Règle du Grognon n° 1

On peut remplacer p boucles for imbriquées, où p est un entier supérieur à 2,

for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
        for(int k=0; k<n; k++)
            ...
			// action

par le code en C :

int v[p], i;
for(i = 0; i < p; i++) v[i] = 0;
while(v[0] < n) { 
	// action
	v[p - 1]++;
	for(i = p - 1; i > 0; i--)
		if(v[i] == n) {
			v[i] = 0; 
			v[i - 1]++;
		}
}

Exemple plus délicat

On veut afficher les combinaisons de p entiers parmi n, c'est à dire des tirages sans remise, où l'ordre n'est pas significatif. À la différence de l'exemple précédent on doit éviter les répétitions. Le code source ex2.c que je propose est le suivant :

/* ex2.c
:w | !gcc % -o .%<
./.%<
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
Tirage de p nombres parmi {0, 1, ... , n - 1} 
SANS remise et sans tenir compte de l'ordre (combinaisons)
Affiche tous les tirages
Exemple pour p = 3 et n = 5 affiche 012 013 014 023 024 034 123 124 134 234 
Retourne le nombre de tirages : nombre de combinaisons de n termes parmi p 
Remplace :
for(int i=0; i<n; i++)
    for(int j=i+1; j<n; j++)
        for(int k=j+1; k<n; k++)
            ...
                ...
avec p boucles for
*/
int cnp(int n, int p);
void print(int p, int v[]);
 
int main(int argc, char *argv[]) 
{
    printf("Affichage des combinaisons de p termes parmi n\n");
    int p = 3, n = 5, c;
    printf("p = %d, n = %d\n", p, n);
    c = cnp(n, p);
    printf("Nombre de combinaisons de %d termes parmi %d: %d\n", p, n, c);
}
 
int
cnp(int n, int p)
{
    int i, c = 0; // indice de boucle for, compteur
    int v[p]; // résultat d'un tirage sous forme de liste de n nombres
    for(i = 0; i < p; i++) // initialisation de v à 0, 1, ... , n - 1
        v[i] = i;
    // On quitte dès que le premier terme atteint n - 1
    while(v[0] <= p - 1) {
        c++;
        print(p, v); // affichage de la liste
        // marche arrière jusqu'au premier terme inférieur à n - 1
        for(i = p - 1; i >= 0 && v[i] == n + i - p; i--);
        v[i++]++; // incrémentation du terme et de l'indice de parcours
        for( ; i < p; i++) // propagation
            v[i] = v[i - 1] + 1; // par des termes successifs
    }
    puts("");
    return c; //compteur
}
 
void 
print(int p, int v[])
{
    // affichage de v sous forme de liste d'ensembles : ... {0, 2, 4} ...
    printf("{");
    for(int i = 0; i < p - 1; i++) 
        printf("%d, ", v[i]);
    printf("%d} ", v[p - 1]);
}

Règle du Grognon n° 2

On peut remplacer les p boucles for (où p est un entier supérieur à 2) :

for(int i=0; i<n; i++)
    for(int j=i+1; j<n; j++)
        for(int k=j+1; k<n; k++)
            ...
            // action 

par le code C :

int v[p];
for(i = 0; i < p; i++)
	v[i] = i;
while(v[0] <= p - 1) {
	// action
	for(i = p - 1; i >= 0 && v[i] == n + i - p; i--);
	v[i++]++;
	for( ; i < p; i++)
		v[i] = v[i - 1] + 1;
}

En python

Voici les transcriptions des programmes précédents en téléchargement ;

ex1.py

ex2.py