Produit cartésien, arrangements et combinaisons avec Access

Objectif : Comment traiter dans Microsoft Access les problèmes de produits cartésiens, d'arrangements ou de combinaisons au moyen de requêtes et de fonctions VBA.

Niveau requis : avancé.

Commentez cet article : 4 commentaires Donner une note à l'article (5)

Article lu   fois.

L'auteur

Profil Pro

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Introduction

Nombreux sont les exemples dans lesquels on a recours à des produits cartésiens, des arrangements ou des combinaisons. Voici une liste de cas concrets :

  • comment afficher les totaux mensuels de factures, y compris pour les mois sans résultats ;
  • comment placer p ouvriers sur n machines à tour de rôle et suivant un roulement ;
  • comment obtenir l'ensemble des dispositions possibles de n ouvriers sur p machines ;
  • comment afficher les différents groupes de p personnes prises parmi n.

L'objectif de cet article est, après avoir introduit ces différents concepts mathématiques, de présenter des exemples de requêtes et de code VBA qui permettent de générer ces ensembles. Pour une meilleure compréhension des choses, on évitera d'utiliser des formules trop complexes.

II. Produit cartésien

En mathématiques, le produit cartésien de deux ensembles X et Y, appelé ensemble-produit, est l'ensemble de tous les couples dont la première composante appartient à X et la seconde à Y.

II-A. Produit cartésien dans une requête

Si on considère X, l'ensemble des enregistrements contenus dans une table t1, et Y l'ensemble des enregistrements d'une table t2, alors l'opérateur de produit cartésien X × Y se traduit en SQL par la requête :

 
Sélectionnez
SELECT t1.*,t2.* FROM t1, t2

Pour illustrer ce cas, j'ai choisi de reprendre les deux premiers exemples mentionnés plus haut dans la liste. Vous pouvez bien sûr les adapter à votre situation.

II-B. Exemples d'application

II-B-1. Combler les mois vides dans une requête de regroupement des montants de factures

Problématique

Disposant de factures et leur montant regroupées par mois, on souhaite afficher les totaux par mois, y compris pour ceux où il n'y a pas de facture.

Liste des étapes

  • On part donc d'une requête regroupement, elle-même basée sur une table T_Facture possédant les champs Article , DateFacture, Volume et PU.
  • On crée ensuite une table d'indices pour les mois de l'année nommée T_IndiceMois comportant un seul champ IndiceMois, et qui contient les entiers compris entre 1 et 12, et une table d'indices pour les années nommée T_IndiceAnnee comportant un seul champ IndiceAnnee.
  • Ensuite, on réalise le produit cartésien entre ces deux tables.
  • Enfin, on compare les mois générés avec le produit cartésien et les données figurant dans la requête de regroupement.

II-B-1-a. Requête de regroupement des montants des factures par mois

Requête R_CA
Sélectionnez
SELECT Year(DateFacture) AS AnnéeCA, Month(DateFacture) AS MoisCA, Sum([volume]*[PU]) AS ValeurCA
FROM T_Facture
GROUP BY Year(DateFacture), Month(T_Facture.DateFacture);

II-B-1-b. Requête réalisant le produit cartésien

Pour afficher les différents mois compris entre 2017 et 20.., on réalise le produit cartésien entre les tables T_IndiceMois et T_IndiceAnnee.

Requête R_Mois
Sélectionnez
SELECT IndiceAnnee, IndiceMois
FROM T_IndiceAnnee, T_IndiceMois;

On dispose désormais de l'ensemble des mois de la période 2017 à 20.., que l'on va pouvoir comparer avec ceux de la requête de regroupement des montants.

II-B-1-c. Requête pour afficher les montants mensuels des factures sur plusieurs années

Pour afficher les montants pour tous les mois compris entre 2017 et 20.., on réalise une jointure gauche entre la requête réalisant le produit cartésien R_Mois et celle réalisant les regroupements.

 
Sélectionnez
SELECT IndiceAnnee, IndiceMois, ValeurCA
FROM R_Mois LEFT JOIN R_CA ON (IndiceAnee=AnneeCA) and (IndiceMois=MoisCA)
ORDER BY IndiceAnnee, IndiceMois;

II-B-2. Roulement dans une usine de p individus sur n machines

Problématique

On souhaite positionner p individus, à tour de rôle et chaque jour, sur n des machines (avec p<=n), de telle sorte que la 1re personne se retrouve sur la 1re machine au bout de n jours. Les données des ouvriers sont enregistrées dans une table T_Personne (NumPersonne, NomPersonne), et celles des machines sont sauvegardées dans une table T_Machine (NumMachine, NomMachine). Le SQL permettant d'afficher l'ensemble de ces configurations pour p<=n est donné par :

R_ProduitCartesien (1)
Sélectionnez
SELECT T_Jour.NumJour, T_Personne.NumPersonne, T_Personne.NomPersonne, (([NumPersonne]-1+[NumJour]-1) Mod 4)+1 AS NumeroMachine
FROM T_Jour, T_Personne
ORDER BY T_Jour.NumJour, T_Personne.NumPersonne;

Dans lequel l'expression :

 
Sélectionnez
NumeroMachine : (([NumPersonne]-1+[NumJour]-1) Mod 4)+1

Donne le numéro de la machine en fonction du numéro de la personne, de celui du jour, et du nombre total de personnes (ici 4).

Pour simplifier, on prendra dans notre exemple p=n.

II-B-2-a. Explication du principe

En mathématiques et en programmation informatique, on désigne par modulo l'opération de calcul du reste de la division euclidienne.

Dans le langage VBA, l'opérateur modulo est désigné par mod. Par exemple, l'expression 1 mod 4 est égale au reste de la division euclidienne de 1 par 4, autrement dit :

 
Sélectionnez
0 mod 4 = 0 - (1\4)*4 = 0
1 mod 4 = 1 - (1\4)*4 = 1
2 mod 4 = 2 - (2\4)*4 = 2
3 mod 4 = 3 - (3\4)*4 = 3
4 mod 4 = 4 - (4\4)*4 = 0
5 mod 4 = 5 - (5\4)*4 = 1
...

\ désigne la division entière.

On voit que l'opérateur mod convient bien pour représenter un roulement.

Si maintenant on reprend, avec des exemples concrets, l'expression donnant l'indice de la machine :

 
Sélectionnez
NumeroMachine : ([NumPersonne]-1+[NumJour]-1) Mod 4)+1

Au début du process, pour la 1re personne, on a :

 
Sélectionnez
NumPersonne = 1
NumJour = 1

NumeroMachine = ((1-1 + 1-1) Mod 4) + 1 = (0 Mod 4) +1 = 0 + 1 = 1

La 1re personne se trouve donc le 1er jour sur la 1re machine.

À ce stade, pour la 2e personne, on a :

 
Sélectionnez
NumPersonne = 2
NumJour = 1

NumeroMachine = ((2-1 + 1-1) Mod 4) + 1 = (1 Mod 4) +1 = 1 + 1 = 2

La 2e personne se trouve donc le 1er jour sur la 2e machine, de la même façon, la 3e personne sur la 3e machine, et le 4e ouvrier sur la 4e machine.

Si maintenant on se place au 2e jour, pour la 1re personne, on a :

 
Sélectionnez
NumPersonne = 1
NumJour = 2

NumeroMachine = ((1-1 + 2-1) Mod 4) + 1 = (1 Mod 4) + 1 = 1 + 1 = 2

La 1re personne se trouve donc le 2e jour sur la 2e machine, elle se trouvera le 3e jour sur la 3e machine, et le 4e sur la 4e machine.

Si on généralise ces résultats à p individus sur n machines (avec p<=n), l'individu d'indice i retrouvera sa machine d'indice i au bout de n jours.

II-B-2-b. Affichage de résultats sur un roulement complet

Exemple de résultats avec les données de départ contenues dans les tables T_Personne et T_Machine, comportant toutes deux quatre enregistrements :

T_Personne

NumPersonne

NomPersonne

1

Dupont

2

Durand

3

Martin

4

Ruffin

T_Machine

NumMachine

NomMachine

1

M1

2

M2

3

M3

4

M4

R_ProduitCartesien (1)

NumJour

NumPersonne

NomPersonne

NumeroMachine

1

1

Dupont

1

1

2

Durand

2

1

3

Martin

3

1

4

Ruffin

4

2

1

Dupont

2

2

2

Durand

3

2

3

Martin

4

2

4

Ruffin

1

3

1

Dupont

3

3

2

Durand

4

3

3

Martin

1

3

4

Ruffin

2

4

1

Dupont

4

4

2

Durand

1

4

3

Martin

2

4

4

Ruffin

3

5

1

Dupont

1

..

..

..

..

II-B-2-c. Roulement inversé pour p >= n

Dans le cas ou le nombre d'individus est supérieur au nombre de machines (avec p>=n), le SQL de la requête devient :

R_ProduitCartesien (2)
Sélectionnez
SELECT T_Jour.NumJour, T_Machine.NumMachine, T_Machine.NomMachine, (([NumMachine]-1+[NumJour]-1) Mod 5)+1 AS NumeroPersonne
FROM T_Jour, T_Machine
ORDER BY T_Jour.NumJour, T_Machine.NumMachine;

Dans lequel l'expression :

 
Sélectionnez
NumeroPersonne : (([NumMachine]-1+[NumJour]-1) Mod 4)+1

Donne le numéro de la personne en fonction du numéro de la machine, de celui du jour, et du nombre total de personnes (ici 4).

La 1re pesonne est sur la 1re machine le 1er jour, la 2e personne se place sur cette machine le 2e jour, la 3e personne se positionne sur elle le 3e jour, et enfin la 4e personne s'y installe le 4e jour.

Si on généralise ces résultats à p individus sur n machines, l'individu d'indice i retrouvera sa machine d'indice i au bout de p jours.

III. Arrangements

En mathématiques, le nombre de façons différentes de prendre p objets parmi n objets en tenant compte de l'ordre est appelé arrangement de p parmi n. Dans le cas où n est égal à p, on parle de permutations.

C'est le cas par exemple pour obtenir l'ensemble des configurations possibles de p ouvriers sur n machines.

III-A. Arrangements affichés dans une requête

Si on considère une table d'individus T_Personne (NumPersonne) comportant n enregistrements, l'ensemble des façons de prendre deux individus parmi n en tenant compte de l'ordre se traduit en SQL par :

Requête R_Arrangements (2)
Sélectionnez
SELECT t1.*,t2.* 
FROM T_Personne As t1, T_Personne As t2 
WHERE (t1.NumPersonne<>t2.NumPersonne)
ORDER BY t1.NumPersonne, t2.NumPersonne;

Suivant le même principe, l'ensemble des façons de prendre trois individus parmi n en tenant compte de l'ordre se traduit en SQL par :

Requête R_Arrangements (3)
Sélectionnez
SELECT t1.*,t2.*, t3.* 
FROM T_Personne As t1, T_Personne As t2, T_Personne As t3 
WHERE (t1.NumPersonne<>t2.NumPersonne) and ((t1.NumPersonne<>t3.NumPersonne) and (t2.NumPersonne<>t3.NumPersonne))
ORDER BY t1.NumPersonne, t2.NumPersonne, t3.NumPersonne;

Dans lequel le critère :

 
Sélectionnez

WHERE (t1.NumPersonne<>t2.NumPersonne) and ((t1.NumPersonne<>t3.NumPersonne) and (t2.NumPersonne<>t3.NumPersonne))

Indique simplement que le numéro d'ordre de la première personne doit être différent de celui de la deuxième personne. Ces deux numéros eux-mêmes différents du troisième.

Le champ NumPersonne de la table T_Personne contient le numéro d'ordre de l'individu.

III-A-1. Affichage de résultats

Liste des arrangements de trois personnes prises parmi quatre, à partir des données contenues dans la table T_Personne :

T_Personne

NumPersonne

NomPersonne

1

Dupont

2

Durand

3

Martin

4

Ruffin

R_Arrangements (3)

NumPersonne1

NomPersonne1

NumPersonne2

NomPersonne2

NumPersonne3

NomPersonne3

1

Dupont

2

Durand

3

Martin

1

Dupont

2

Durand

4

Ruffin

1

Dupont

3

Martin

2

Durand

1

Dupont

3

Martin

4

Ruffin

1

Dupont

4

Ruffin

2

Durand

1

Dupont

4

Ruffin

3

Martin

2

Durand

1

Dupont

3

Martin

2

Durand

1

Dupont

4

Ruffin

2

Durand

3

Martin

1

Dupont

2

Durand

3

Martin

4

Ruffin

2

Durand

4

Ruffin

1

Dupont

2

Durand

4

Ruffin

3

Martin

3

Martin

1

Dupont

2

Durand

3

Martin

1

Dupont

4

Ruffin

3

Martin

2

Durand

1

Dupont

3

Martin

2

Durand

4

Ruffin

3

Martin

4

Ruffin

1

Dupont

3

Martin

4

Ruffin

2

Durand

4

Ruffin

1

Dupont

2

Durand

4

Ruffin

1

Dupont

3

Martin

4

Ruffin

2

Durand

1

Dupont

4

Ruffin

2

Durand

3

Martin

4

Ruffin

3

Martin

1

Dupont

4

Ruffin

3

Martin

2

Durand

III-B. Arrangements générés avec du code VBA

L'objectif est d'alimenter par du code une table T_Arrangements (NumeroArrangement, NumeroOrdre, Indice), pour obtenir l'ensemble des nombres entiers constituant les arrangements, classés par numéro d'arrangement et numéro d'ordre.

Une fonction récursive appelée dans une fonction principale permet d'insérer dans une table la liste des arrangements de p entiers pris dans n :

fonction récursive
Sélectionnez
'*********************************************************************************************************************
'*********************Fonction récursive pour générer les arrangements de p entiers pris parmi n**********************
'*********************************************************************************************************************
Public Function Arrangements(rs As DAO.Recordset, ByVal n As Long, ByVal p As Long, ByVal t As Variant, ind As Long)
'rs : recordset basé sur la table t_arrangements pour enregistrer les arrangements
'n : nombre total d'entiers
'p : nombre d'entiers tirés
't : tableau contenant les p entiers constituant un arrangement
'ind : indice de l'arrangement
Dim i As Long, j As Long

   If p <> 0 Then
      
      For i = 1 To n
         If Not Trouve(t, i) Then ' Non encore généré, non présent dans la liste.
            t(UBound(t) - p + 1) = i
            Arrangements rs, n, p - 1, t, ind ' appel récursif de la fonction pour p-1
         End If
   
      Next i
   Else
      For j = LBound(t) To UBound(t) ' parcours du tableau des p entiers
         rs.AddNew ' sauvegarde des p entiers constituant l'arrangement
         rs!NumeroArrangement = ind
         rs!NumeroOrdre = j
         rs!Indice = t(j)
         rs.Update
      Next j
      ind = ind + 1 ' On passe à l'indice du prochain arrangement
   End If

End Function

Une fonction principale permettant d'appeler la sous-routine :

fonction appelante
Sélectionnez
'*********************************************************************************************************************
'*********************Fonction appelante pour générer les arrangements de p entiers pris parmi n**********************
'*********************************************************************************************************************
Public Function GenererArrangements(n As Long, p As Long)
'n : nombre total d'entiers
'p : nombre d'entiers tirés
Dim db As DAO.Database ' Variable liée à la base de données
Dim rs As DAO.Recordset ' Recordset lié à la table T_Arrangements
Dim t() As Long

ReDim t(1 To p) As Long ' Dimensionnement du tableau des arrangements

Set db = CurrentDb
Set rs = db.OpenRecordset("T_Arrangements", dbOpenDynaset) ' Ouverture de la table

DoCmd.SetWarnings False
DoCmd.RunSQL ("delete * from T_Arrangements;") ' On vide la table
DoCmd.SetWarnings True

Call Arrangements(rs, n, p, t, 1) ' Appel de la fonction récursive

' Libération des variables
rs.Close
Set rs = Nothing

Set db = Nothing

End Function

III-C. Application : Répartitions de n ouvriers sur p machines

On souhaite obtenir l'ensemble des dispositions possibles de n ouvriers sur p machines, afin d'évaluer celle qui offre le meilleur rendement. Les données des ouvriers sont enregistrées dans une table T_Personne (NumPersonne, NomPersonne), et celles des machines sont sauvegardées dans une table T_Machine (NumMachine, NomMachine).

III-C-1. Table T_Arrangements

Table permettant d'enregistrer les différentes dispositions de n personnes sur p machines.

T_Arrangements
Nom du champ  Type du champ  Description 
NumeroArrangement  Entier long  Numéro de l'arrangement 
NumeroMachine  Entier long  Numéro de la machine 
NumeroPersonne  Entier long  Numéro de la personne 

III-C-2. Code VBA permettant de générer les répartitions

L'objectif est d'alimenter par du code une table T_Arrangements, pour obtenir l'ensemble des dispositions constituant les arrangements classés par numéro d'arrangement et numéro de machine.

Une fonction récursive appelée dans une fonction principale permet d'insérer dans la table la liste des arrangements de n ouvriers placés sur p machines (avec p<=n) :

fonction récursive
Sélectionnez
'*********************************************************************************************************************
'*******************Fonction récursive pour générer les arrangements de n ouvriers sur p machines*********************
'*********************************************************************************************************************
Public Function Arrangements(rs1 As DAO.Recordset, rs2 As DAO.Recordset, ByVal p As Long, ByVal t As Variant, ind As Long)
'rs1 : recordset basé sur la table t_personne pour enregistrer les n personnes
'rs2 : recordset basé sur la table t_arrangements pour enregistrer les arrangements
'p : nombre d'entiers tirés
't : tableau contenant les p numéros de personnes constituant un arrangement
'ind : indice de l'arrangement
Dim i As Long, j As Long ' Indice
Dim debut As Variant ' Signet de début

   If p <> 0 Then
      rs1.MoveFirst ' Positionnement au début du jeu d'enregistrements
      Do Until rs1.EOF ' On parcourt les n enregistrements
         If Not Trouve(t, rs1!NumPersonne) Then ' Non encore généré, non présent dans la liste.
            debut = rs1.Bookmark ' Pointeur courant
            t(UBound(t) - p + 1) = rs1!NumPersonne ' Sauvegarde du numéro de personne
            Arrangements rs1, rs2, p - 1, t, ind  ' Appel récursif de la fonction pour p-1
            rs1.Bookmark = debut ' Retour au pointeur courant
         End If
         rs1.MoveNext
      Loop
      
   Else
      For j = LBound(t) To UBound(t) ' Parcours du tableau des p numéros de personnes
         rs2.AddNew ' Sauvegarde des p numéros de personnes constituant l'arrangement
         rs2!NumeroArrangement = ind ' Indice de l'arrangement
         rs2!NumeroMachine = j ' Numéro de machine
         rs2!NumeroPersonne = t(j) ' Numéro de personne
         rs2.Update
      Next j
      ind = ind + 1 ' On passe à l'indice du prochain arrangement
   End If

End Function

Une fonction principale permettant d'appeler la sous-routine :

fonction appelante
Sélectionnez
'******************************************************************************************************************
'*******************Fonction appelante pour générer les arrangements de n ouvriers sur p machines******************
'******************************************************************************************************************
Public Function GenererArrangements(p As Long)
'p : nombre de personnes choisies
Dim db As DAO.Database
Dim rs1 As DAO.Recordset ' Recordset lié à la table T_Personne
Dim rs2 As DAO.Recordset ' Recordset lié à la table T_Arrangements
Dim t() As Long ' Tableau des indices des personnes

ReDim t(1 To p) As Long ' Dimensionnement du tableau des arrangements

Set db = CurrentDb
Set rs1 = db.OpenRecordset("T_Personne", dbOpenDynaset) ' Ouverture de la table T_Personne
Set rs2 = db.OpenRecordset("T_Arrangements", dbOpenDynaset) ' Ouverture de la table T_Arrangements

DoCmd.SetWarnings False
DoCmd.RunSQL ("delete * from T_Arrangements;") ' On vide la table
DoCmd.SetWarnings True

Call Arrangements(rs1, rs2, p, t, 1) ' Appel de la fonction récursive

' Libération des variables
rs1.Close
Set rs1 = Nothing

rs2.Close
Set rs2 = Nothing

Set db = Nothing

End Function

III-C-3. Affichage de résultats

Extrait des résultats de la requête R_Arrangements, avec quatre personnes et trois machines :

R_Arrangements

NumeroArrangement

NumeroMachine

NomMachine

NumeroPersonne

NomPersonne

1

1

M1

1

Dupont

1

2

M2

2

Durand

1

3

M3

3

Martin

2

1

M1

1

Dupont

2

2

M2

3

Martin

2

3

M3

2

Durand

..

..

..

..

..

23

1

M1

4

Ruffin

23

2

M2

3

Martin

23

3

M3

1

Dupont

24

1

M1

4

Ruffin

24

2

M2

3

Martin

24

3

M3

2

Durand

La requête R_Arrangements relie les tables T_Arrangements, T_Machine et T_Personne.

IV. Combinaisons

En mathématiques, le nombre de façons différentes de prendre p objets parmi n objets sans tenir compte de l'ordre est appelé combinaisons de p parmi n.

C'est le cas quand on souhaite afficher les différents groupes de p individus pris parmi n.

IV-A. Combinaisons affichées dans une requête

Si on considère une table d'individus T_Personne (NumPersonne) comportant n enregistrements. L'ensemble des façons de prendre deux individus parmi n sans tenir compte de l'ordre se traduit en SQL par :

Requête R_Combinaisons (2)
Sélectionnez
SELECT t1.*,t2.* 
FROM T_Personne As t1, T_Personne As t2 
WHERE (t1.NumPersonne<t2.NumPersonne)
ORDER BY t1.NumPersonne, t2.NumPersonne;

Suivant le même principe, l'ensemble des manières de prendre trois individus parmi n sans tenir compte de l'ordre se traduit en SQL par :

Requête R_Combinaisons (3)
Sélectionnez
SELECT t1.*,t2.*, t3.* 
FROM T_Personne As t1, T_Personne As t2, T_Personne As t3 
WHERE (t1.NumPersonne<t2.NumPersonne) and (t2.NumPersonne<t3.NumPersonne)
ORDER BY t1.NumPersonne, t2.NumPersonne, t3.NumPersonne;

Dans lequel le critère :

 
Sélectionnez
WHERE (t1.NumPersonne<t2.NumPersonne) and (t2.NumPersonne<t3.NumPersonne)

Indique simplement que le numéro d'ordre de la première personne doit être plus petit que celui de la deuxième personne. Lui-même plus petit que celui de la troisième.

IV-A-1. Affichage de résultat

Liste des combinaisons de trois personnes prises parmi quatre, à partir des données contenues dans la table T_Personne :

R_Combinaisons (3)

NumPersonne1

NomPersonne1

NumPersonne2

NomPersonne2

NumPersonne3

NomPersonne3

1

Dupont

2

Durand

3

Martin

1

Dupont

2

Durand

4

Ruffin

1

Dupont

3

Martin

4

Ruffin

2

Durand

3

Martin

4

Ruffin

IV-B. Combinaisons générées avec du code VBA

L'objectif est d'alimenter par du code une table T_Combinaisons (NumeroCombinaison, NumeroOrdre, Indice), pour obtenir l'ensemble des nombres entiers constituant les combinaisons, classés par numéro d'arrangement et numéro d'ordre.

Une fonction récursive appelée dans une fonction principale permet d'insérer dans une table la liste des combinaisons de p entiers pris dans n :

fonction récursive
Sélectionnez
'*********************************************************************************************************************
'********************Fonction récursive pour générer les combinaisons de p entiers pris parmi n***********************
'*********************************************************************************************************************
Public Function Combinaisons(rs As DAO.Recordset, ByVal n As Long, ByVal p As Long, j As Long, ByVal t As Variant, ind As Long)
'rs : recordset basé sur la table t_combinaisons pour enregistrer les combinaisons
'n : nombre total d'entiers
'p : nombre d'entiers tirés
't : tableau contenant les p entiers constituant une combinaison
'ind : indice de la combinaison
Dim i As Long, k As Long

   If p <> 0 Then
      For i = 1 To n ' On parcourt les n indices
   
         If (i > j) Then ' Pris en compte car supérieur au précédent.
            t(UBound(t) - p + 1) = i
            Combinaisons rs, n, p - 1, i, t, ind ' Appel récursif de la fonction pour p-1
         End If
   
      Next i
   Else
        For k = LBound(t) To UBound(t) ' Parcours du tableau des p entiers
         rs.AddNew ' Sauvegarde des p entiers constituant la combinaison
         rs!NumeroCombinaison = ind
         rs!NumeroOrdre = k
         rs!Indice = t(k)
         rs.Update
      Next k
      ind = ind + 1 ' On passe à l'indice de la prochaine combinaison
   End If

End Function

Une fonction principale permettant d'appeler la sous-routine :

fonction appelante
Sélectionnez
'*********************************************************************************************************************
'********************Fonction appelante pour générer les combinaisons de p entiers pris parmi n***********************
'*********************************************************************************************************************
Public Function GenererCombinaisons(n As Long, p As Long)
'n : nombre total d'entiers
'p : nombre d'entiers tirés
Dim db As DAO.Database ' Variable liée à la base de données
Dim rs As DAO.Recordset ' Recordset lié à la table T_Combinaisons
Dim t() As Long ' Tableau des indices

ReDim t(1 To p) As Long ' Dimensionnement du tableau des combinaisons

Set db = CurrentDb
Set rs = db.OpenRecordset("T_Combinaisons", dbOpenDynaset) ' Ouverture de la table

DoCmd.SetWarnings False
DoCmd.RunSQL ("delete * from T_Combinaisons;") ' On vide la table
DoCmd.SetWarnings True

Call Combinaisons(rs, n, p, 0, t, 1) ' Appel de la fonction récursive

' Libération des variables
rs.Close
Set rs = Nothing

Set db = Nothing

End Function

IV-C. Application : Ensemble des groupes de p personnes prises parmi n

On souhaite obtenir l'ensemble des dispositions possibles de p individus pris parmi n, afin d'évaluer le groupe le plus efficace pour effectuer un travail donné. Les données des individus sont enregistrées dans une table T_Personne (NumPersonne, NomPersonne).

IV-C-1. Table T_Combinaisons

Table permettant d'enregistrer les différentes équipes de p individus pris parmi n.

T_Combinaisons
Nom du champ  Type du champ  Description 
NumeroCombinaison  Entier long  Numéro de la combinaison 
NumeroOrdre  Entier long  Numéro d'ordre 
NumeroPersonne  Entier long  Numéro de la personne 

IV-C-2. Code VBA permettant de générer les groupes

L'objectif est d'alimenter par du code une table T_Combinaisons, pour obtenir l'ensemble des équipes constituant les combinaisons classées par numéro de combinaison et numéro d'ordre.

Une fonction récursive appelée dans une fonction principale permet d'insérer dans la table la liste des combinaisons de p individus pris parmi n (avec p<=n) :

fonction récursive
Sélectionnez
'******************************************************************************************************************
'******************Fonction récursive pour générer les combinaisons de p individus pris parmi n********************
'******************************************************************************************************************
Public Function Combinaisons(rs1 As DAO.Recordset, rs2 As DAO.Recordset, ByVal p As Long, j As Long, ByVal t As Variant, ind As Long)
'rs1 : recordset basé sur la table t_personne pour enregistrer les personnes
'rs2 : recordset basé sur la table t_combinaisons pour enregistrer les combinaisons
'p : nombre d'entiers tirés
't : tableau contenant les p entiers constituant une combinaison
'ind : indice de la combinaison
Dim k As Long
Dim debut As Variant

   If p <> 0 Then
      rs1.MoveFirst ' Positionnement au début du jeu d'enregistrements
      Do Until rs1.EOF ' On parcourt les n enregistrements
    
         If (rs1!NumPersonne > j) Then ' Pris en compte car supérieur au précédent.
            debut = rs1.Bookmark ' Pointeur courant
            t(UBound(t) - p + 1) = rs1!NumPersonne ' Sauvegarde du numéro de personne
            Combinaisons rs1, rs2, p - 1, rs1!NumPersonne, t, ind  ' Appel récursif de la fonction pour p-1
            rs1.Bookmark = debut ' Retour au pointeur courant
         End If
         
         rs1.MoveNext
         
      Loop
      
   Else
        For k = LBound(t) To UBound(t) ' Parcours du tableau des p entiers
         rs2.AddNew ' Sauvegarde des p numéros de personnes constituant la combinaison
         rs2!NumeroCombinaison = ind
         rs2!NumeroOrdre = k '
         rs2!NumeroPersonne = t(k) ' Numéro de personne
         rs2.Update
      Next k
      ind = ind + 1 ' On passe à l'indice de la prochaine combinaison
   End If

End Function

Une fonction principale permettant d'appeler la sous-routine :

fonction appelante
Sélectionnez
'******************************************************************************************************************
'*******************Fonction appelante pour générer les combinaisons de p individus pris parmi n*******************
'******************************************************************************************************************
Public Function GenererCombinaisons(p As Long)
'p : nombre d'entiers tirés
Dim db As DAO.Database
Dim rs1 As DAO.Recordset ' Recordset lié à la table T_Personne
Dim rs2 As DAO.Recordset ' Recordset lié à la table T_Combinaisons
Dim t() As Long ' Tableau des indices

ReDim t(1 To p) As Long ' Dimensionnement du tableau des combinaisons

Set db = CurrentDb
Set rs1 = db.OpenRecordset("T_Personne", dbOpenSnapshot) ' Ouverture de la table T_Personne
Set rs2 = db.OpenRecordset("T_Combinaisons", dbOpenDynaset) ' Ouverture de la table T_Combinaisons

DoCmd.SetWarnings False
DoCmd.RunSQL ("delete * from T_Combinaisons;") ' On vide la table
DoCmd.SetWarnings True

Call Combinaisons(rs1, rs2, p, 0, t, 1) ' Appel de la fonction récursive

' Libération des variables
rs1.Close
Set rs1 = Nothing

rs2.Close
Set rs2 = Nothing

Set db = Nothing

End Function

IV-C-3. Affichage de résultats

Extrait des résultats de la requête R_Combinaisons, avec trois personnes prises parmi quatre :

R_Combinaisons

NumeroCombinaison

NumeroOrdre

NumeroPersonne

NomPersonne

1

1

1

Dupont

1

2

2

Durand

1

3

3

Martin

2

1

1

Dupont

2

2

2

Durand

2

3

4

Ruffin

3

1

1

Dupont

3

2

3

Martin

3

3

4

Ruffin

4

1

2

Durand

4

2

3

Martin

4

3

4

Ruffin

La requête R_Combinaisons relie les tables T_Combinaisons et T_Personne.

V. La base de données à télécharger

La base jointeBD Combinatoire présente les différents exemples décrits dans le tutoriel, elle est au format Access 2000.

VI. Remerciements

Je tiens à remercier Pierre Fauconnier et arkham46 pour m'avoir conseillé pour la réalisation de cet article, ainsi que Claude Leloup pour sa relecture.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Copyright © 2017 Denis Hulo. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts. Droits de diffusion permanents accordés à Developpez LLC.