Calculs de tous les arrangements (mathématiques) avec une requête SQL

Certains pensent impossible de réaliser des traitements mathématiques complexes à l’aide de requêtes SQL. Voici la démonstration que SQL n’a pas de limite, du fait qu’il s’agit d’un langage complet…
En une seule requête voici le calcul de tous les arrangements possible d’un ensemble de données…

Une seule requête, bien sûre récursive, est nécessaire pour traiter ce problème…

Commençons par créer la table qui nous servira de test :
CREATE TABLE T_CMB (CMB_DATA VARCHAR(8))

Ajoutons lui des données, en nous assurans qu’un caractère joker, par exemple le point virgule (;) n’existe pas dans les données, car il va

servir de joker pour notre requête :
INSERT INTO T_CMB VALUES ('ABC')
INSERT INTO T_CMB VALUES ('DEF')
INSERT INTO T_CMB VALUES ('GHI')

La requête suivante réalise toutes les permutations des données de départ


WITH
T_DATA AS  
(SELECT CMB_DATA, 1 AS COMBINAISON,  
        ROW_NUMBER() OVER(ORDER BY CMB_DATA) AS ORDRE,
        COUNT(*) OVER() AS N
 FROM   T_CMB),
T_RECUR AS
(SELECT CAST(CMB_DATA AS VARCHAR(max)) +';' AS CMB_DATA, COMBINAISON, ORDRE, N
 FROM   T_DATA
 UNION  ALL
 SELECT T1.CMB_DATA + ';' + T2.CMB_DATA, T2.COMBINAISON + 1, ROW_NUMBER() OVER(PARTITION BY T1.COMBINAISON ORDER BY T2.CMB_DATA) ORDRE, T1.N
 FROM   T_DATA AS T1
        CROSS JOIN T_RECUR AS T2
 WHERE  T2.COMBINAISON < T1.N
 -- this line must be delete if you want a repetitive permutation  
   AND  T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'),
T_COMBINE AS
(SELECT CMB_DATA, ROW_NUMBER() OVER(ORDER BY CMB_DATA) AS ORDRE
 FROM   T_RECUR
 WHERE  COMBINAISON = N),
T_N AS
(SELECT 1 AS N
 UNION  ALL
 SELECT N + 1
 FROM   T_N
 WHERE  N + 1 <= ALL (SELECT LEN(CMB_DATA)
                      FROM   T_COMBINE)),
T_SOL AS
(SELECT  *, REVERSE(SUBSTRING(CMB_DATA, 1, N-1)) AS SOUS_CHAINE,
            REVERSE(SUBSTRING(REVERSE(SUBSTRING(CMB_DATA, 1, N-1)), 1,  
                                        CASE  
                                           WHEN CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N-1))) - 1 = -1 THEN LEN(CMB_DATA)
                                           ELSE CHARINDEX(';', REVERSE(SUBSTRING(CMB_DATA, 1, N-1))) - 1
                                        END)) AS DATA
 FROM    T_COMBINE
         INNER JOIN  T_N                
               ON SUBSTRING(CMB_DATA, N, 1) = ';')
SELECT DATA AS CMB_DATA, ORDRE AS PERMUTATION
FROM   T_SOL

Cette requête tourne sur MS SQL Server et peut être adaptée à tous les SGBDR qui mettent en œuvre les requêtes récursives via la CTE (pour plus de détail sur la CTE, voir : http://sqlpro.developpez.com/cours/sqlserver/cte-recursives/)

Résultat :


CMB_DATA                  PERMUTATION
------------------------- --------------------
ABC                       1
DEF                       1
GHI                       1
 
ABC                       2
GHI                       2
DEF                       2
 
DEF                       3
ABC                       3
GHI                       3
 
DEF                       4
GHI                       4
ABC                       4
 
GHI                       5
ABC                       5
DEF                       5
 
GHI                       6
DEF                       6
ABC                       6

Si vous voulez un arrangement avec des données répétitives, vous devez simplement retirer la ligne 18 :
AND  T2.CMB_DATA NOT LIKE '%' + T1.CMB_DATA +';%'
Ce qui donne :


CMB_DATA                PERMUTATION
----------------------- --------------------
ABC                     1
ABC                     1
ABC                     1
 
ABC                     2
ABC                     2
DEF                     2
 
ABC                     3
ABC                     3
GHI                     3
 
ABC                     4
DEF                     4
ABC                     4
 
ABC                     5
DEF                     5
DEF                     5
 
ABC                     6
DEF                     6
GHI                     6
 
ABC                     7
GHI                     7
ABC                     7
 
ABC                     8
GHI                     8
DEF                     8
 
ABC                     9
GHI                     9
GHI                     9
 
DEF                     10
ABC                     10
ABC                     10
 
DEF                     11
ABC                     11
DEF                     11
 
DEF                     12
ABC                     12
GHI                     12
 
DEF                     13
DEF                     13
ABC                     13
 
DEF                     14
DEF                     14
DEF                     14
 
DEF                     15
DEF                     15
GHI                     15
 
DEF                     16
GHI                     16
ABC                     16
 
DEF                     17
GHI                     17
DEF                     17
 
DEF                     18
GHI                     18
GHI                     18
 
GHI                     19
ABC                     19
ABC                     19
 
GHI                     20
ABC                     20
DEF                     20
 
GHI                     21
ABC                     21
GHI                     21
 
GHI                     22
DEF                     22
ABC                     22
 
GHI                     23
DEF                     23
DEF                     23
 
GHI                     24
DEF                     24
GHI                     24
 
GHI                     25
GHI                     25
ABC                     25
 
GHI                     26
GHI                     26
DEF                     26
 
GHI                     27
GHI                     27
GHI                     27

CQFD !

Une solution utilisant les puissances de 2 et XML m’a été données par Ryan Randall, sur le forum de sqlservercental. Je vous la livre brute de fonderie :


-- paramétre pour gestion de la duplication ou non  
DECLARE @AllowDuplicates BIT;  
SET @AllowDuplicates = 0;  
 
WITH  
  a AS (SELECT COUNT(*) AS cnt  
        FROM   T_CMB)  
, b AS (SELECT POWER(2, ROW_NUMBER() OVER(ORDER BY CMB_DATA)-1) AS marker, CMB_DATA  
        FROM   T_CMB)  
, c AS (SELECT marker, 1 as level, CAST('<x>' + CMB_DATA + '</x>' AS VARCHAR(MAX)) AS CMB_DATA  
        FROM   b  
        UNION  ALL  
        SELECT c.marker + b.marker, c.level + 1, c.CMB_DATA + '<x>' + b.CMB_DATA + '</x>' AS CMB_DATA
        FROM   b  
               INNER JOIN c  
                     ON (@AllowDuplicates = 1 OR b.marker & c.marker = 0)  
        WHERE  c.level < (SELECT cnt  
                          FROM   a))  
, d AS (SELECT ROW_NUMBER() OVER(ORDER BY CMB_DATA) as permutation, CAST(CMB_DATA AS XML) AS CMB_DATA
        FROM   c  
        WHERE level = (SELECT cnt  
                       FROM   a))  
SELECT  c.value('.', 'varchar(max)') AS CMB_DATA,
        d.permutation
FROM    d  
        CROSS APPLY CMB_DATA.nodes('//x') T(c)

Origine : http://www.sqlservercentral.com/Forums/Topic218243-186-2.aspx?Update=1

L’utilisation des puissance de deux me convient, cependant l’usage de xml sort du SQL traditionnel. Reste à voir à l’usage celle qui aura les meilleures performances !


Frédéric BROUARD, Spécialiste modélisation, bases de données, optimisation, langage SQL.
Le site sur le langage SQL et les S.G.B.D. relationnels : http://sqlpro.developpez.com/
Expert SQL Server http://www.sqlspot.com : audit, optimisation, tuning, formation
* * * * * Enseignant au CNAM PACA et à l’ISEN à Toulon * * * * *

2 réflexions au sujet de « Calculs de tous les arrangements (mathématiques) avec une requête SQL »

  1. Avatar de sqlprosqlpro Auteur de l’article

    Cette requête donne 3 colonnes, là ou nous avons besoin d’une seule. Ensuite nous n’avons pas d’identifiant de chacune des permutations (il faudrait ajouter une 4e colonne). A noter, le produit cartésien se fait avec un CROSS JOIN depuis la norme SQL de 1992…

Laisser un commentaire