Pour des valeurs relativement petites de n(20 dans cet exemple), vous pouvez utiliser une méthode qui exploite le fait que les entiers naturels sont des combinaisons de bits.
Solution T-SQL
Exemples de données:
DECLARE @Sample AS TABLE
(
item_id tinyint IDENTITY(1,1) PRIMARY KEY NONCLUSTERED,
item nvarchar(500) NOT NULL,
bit_value AS
CONVERT
(
integer,
POWER(2, item_id - 1)
)
PERSISTED UNIQUE CLUSTERED
);
INSERT @Sample
(item)
VALUES
(N'Ann'),
(N'Bob'),
(N'Charles'),
(N'Darren'),
(N'Eric'),
(N'Fred'),
(N'George'),
(N'Harry'),
(N'Ian'),
(N'John'),
(N'Keith'),
(N'Larry'),
(N'Mark'),
(N'Nathan'),
(N'Owen'),
(N'Paul'),
(N'Quentin'),
(N'Ryan'),
(N'Steve'),
(N'Terry');
Solution:
-- Maximum integer we need
-- for all combinations of 'n' bits
DECLARE
@max integer =
POWER(2,
(
SELECT COUNT(*)
FROM @Sample AS s
)
) - 1;
SELECT
combination =
STUFF
(
(
-- Choose items where the bit is set
-- and concatenate all matches
SELECT ',' + s.item
FROM @Sample AS s
WHERE
n.n & s.bit_value = s.bit_value
ORDER BY
s.bit_value
FOR XML
PATH (''),
TYPE
).value('(./text())[1]', 'varchar(8000)'), 1, 1, ''
)
-- A standard numbers table
-- (single column, integers from 1 to 1048576, indexed)
FROM dbo.Numbers AS N
WHERE
N.n BETWEEN 1 AND @max;
Échantillon de sortie:
╔════════════════════════╗
║ combination ║
╠════════════════════════╣
║ Ann ║
║ Bob ║
║ Ann,Bob ║
║ Charles ║
║ Ann,Charles ║
║ Bob,Charles ║
║ Ann,Bob,Charles ║
║ Darren ║
║ Ann,Darren ║
║ Bob,Darren ║
║ Ann,Bob,Darren ║
║ Charles,Darren ║
║ Ann,Charles,Darren ║
║ Bob,Charles,Darren ║
║ Ann,Bob,Charles,Darren ║
║ ... ║
╚════════════════════════╝
Plan d'exécution:
Il faut 41 secondes pour écrire les 1 048 576 combinaisons dans une variable de mon ordinateur portable. Avec le parallélisme forcé, j'ai pu réduire le temps d'exécution DOP 8à 13 secondes.
Si vous avez besoin d'une table Numbers, c'est un moyen rapide d'en produire une:
SELECT TOP (1048576)
n = ISNULL(CONVERT(integer, ROW_NUMBER() OVER (ORDER BY (SELECT NULL))), 0)
INTO dbo.Numbers
FROM sys.columns AS c
CROSS JOIN sys.columns AS c2
CROSS JOIN sys.columns AS c3;
CREATE UNIQUE CLUSTERED INDEX cuq
ON dbo.Numbers (n)
WITH (MAXDOP = 1, SORT_IN_TEMPDB = ON);
Solution SQLCLR
Une implémentation beaucoup plus efficace est possible dans SQLCLR (SQL Server 2005 et suivants):
CREATE ASSEMBLY [Demo]
AUTHORIZATION [dbo]
FROM 0x4D5A90000300000004000000FFFF0000B800000000000000400000000000000000000000000000000000000000000000000000000000000000000000800000000E1FBA0E00B409CD21B8014CCD21546869732070726F6772616D2063616E6E6F742062652072756E20696E20444F53206D6F64652E0D0D0A2400000000000000504500004C0103000705BC500000000000000000E00002210B010800001000000006000000000000EE2E00000020000000400000000040000020000000020000040000000000000004000000000000000080000000020000000000000300408500001000001000000000100000100000000000001000000000000000000000009C2E00004F000000004000009802000000000000000000000000000000000000006000000C000000042E00001C0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000080000000000000000000000082000004800000000000000000000002E74657874000000F40E0000002000000010000000020000000000000000000000000000200000602E7273726300000098020000004000000004000000120000000000000000000000000000400000402E72656C6F6300000C0000000060000000020000001600000000000000000000000000004000004200000000000000000000000000000000D02E0000000000004800000002000500B82200004C0B00000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000133002003C00000001000011280E00000A6F0F00000A027B030000043315027B020000041FFE330B02167D02000004020A2B0716730C0000060A06027B050000047D04000004062A1E0228050000062A133005006101000002000011027B020000040C0845020000000500000024010000384501000002157D0200000402027B04000004178D0F0000010D09161F2C9D096F1000000A7D0600000402027B060000048E698D110000017D0700000402230000000000000040027B060000048E696C281100000A6917597D08000004160A2B1D027B0700000406230000000000000040066C281100000A699E0617580A06027B070000048E6932D802177D0A00000438A4000000027E1200000A7D09000004160B2B3D027B0A000004027B0700000407945F027B070000040794332002257B09000004027B06000004079A1F2C8C0F000001281300000A7D090000040717580B07027B070000048E692F10027B0A000004027B0700000407942FA802027B0900000416027B090000046F1400000A17596F1500000A7D0100000402177D02000004172A02157D0200000402257B0A00000417587D0A000004027B0A000004027B080000043E4BFFFFFF162A1E027B010000042A1A731600000A7A1330000001000000030000112A1E027B010000042A7A02281700000A02037D0200000402280E00000A6F0F00000A7D030000042A1330020011000000010000111FFE730C0000060A06027D05000004062AD60202176320555555555F5910000220333333335F02186320333333335F58100002021A6358200F0F0F0F5F20010101015A1F18632A2603027410000001512A1E02281700000A2A00000042534A4201000100000000000C00000076322E302E35303732370000000005006C00000088030000237E0000F4030000F404000023537472696E677300000000E80800000800000023555300F0080000100000002347554944000000000900004C02000023426C6F6200000000000000020000015717A20B0902000000FA2533001600000100000014000000030000000A0000000C0000000500000005000000180000000B00000003000000010000000200000002000000070000000200000001000000020000000100000000000A00010000000000060038003100060052003F000600BF00A0000600DF00CC001300F30000000600220102010600420102010A008C0171010600CA01AF010600D801AF010600E6013F000600F201310006002804CC0006005104400406007E0431000600830431000600900431000600960431000600C10431000600D70402010000000001000000000001000100010010001300000005000100010003011000A101000005000100050001008602C20101002F03CE0101003A03CE0106008400D10106007A03D10106008B03D40106009A03D8010600A703CE010600B303D1010600BB03CE0150220000000096005E000A0001006D22000000009100660010000200A322000000009600760015000300AD220000000086187E001C000500502000000000E101FE01A8010500982000000000E1015002B9010500A02000000000E1017D02BE0105000D2200000000E1099302C5010500152200000000E101E1021C0005001C2200000000E1010C031C000500292200000000E1094F03C501050031220000000086187E0026000500000001008400000001009000000001009200020002009400000001002F03030006000300090003000A0003002D000300310019007E001C0021007E00200031007E00260039007E001C0041007E001C000C004202B00111004202B90159007D02BE011400D502C901590006031C00610027031C005900D502C50169007E001C0071005804E50171006A04EA0181008A04F30191009B04FA0181009F04D1018100A50400028100AC04EA018100B704070299007E001C0009007E001C00A1007E001C0020002B002B002E0013001A022E0023002C022E001B0023026300C300E001A0006B00E001C0006B00E00100016B00E00120016B00E00160016B00E00180016B00E001EE010D021502030001000000C303DC0100000104DC0102000800030002000B00050003000A000D0003000C000F0003000E0011000300100013000300120015000300140017000300160019009C01A2010480000000000000000000000000000000006001000002000000000000000000000001002800000000000200000000000000000000000100650100000000030002000000003C4D6F64756C653E0044656D6F2E646C6C0055736572446566696E656446756E6374696F6E73006D73636F726C69620053797374656D004F626A6563740053797374656D2E436F6C6C656374696F6E730049456E756D657261626C65005065726D757465004E756D6265724F66536574426974730046696C6C526F77002E63746F7200456C656D656E74734353560069006F005065726D75746174696F6E0053797374656D2E52756E74696D652E496E7465726F705365727669636573004F75744174747269627574650053797374656D2E446961676E6F73746963730044656275676761626C6541747472696275746500446562756767696E674D6F6465730053797374656D2E52756E74696D652E436F6D70696C6572536572766963657300436F6D70696C6174696F6E52656C61786174696F6E734174747269627574650052756E74696D65436F6D7061746962696C6974794174747269627574650044656D6F0053797374656D2E44617461004D6963726F736F66742E53716C5365727665722E5365727665720053716C46756E6374696F6E417474726962757465003C5065726D7574653E645F5F300053797374656D2E436F6C6C656374696F6E732E47656E657269630049456E756D657261626C6560310049456E756D657261746F7260310049456E756D657261746F720049446973706F7361626C650053797374656D2E436F6C6C656374696F6E732E47656E657269632E49456E756D657261626C653C53797374656D2E4F626A6563743E2E476574456E756D657261746F7200476574456E756D657261746F720053797374656D2E436F6C6C656374696F6E732E49456E756D657261626C652E476574456E756D657261746F72004D6F76654E657874003C3E325F5F63757272656E740053797374656D2E436F6C6C656374696F6E732E47656E657269632E49456E756D657261746F723C53797374656D2E4F626A6563743E2E6765745F43757272656E74006765745F43757272656E740053797374656D2E436F6C6C656374696F6E732E49456E756D657261746F722E52657365740052657365740053797374656D2E49446973706F7361626C652E446973706F736500446973706F7365003C3E315F5F7374617465003C3E6C5F5F696E697469616C54687265616449640053797374656D2E436F6C6C656374696F6E732E49456E756D657261746F722E6765745F43757272656E74003C3E335F5F456C656D656E7473435356003C656C656D656E74733E355F5F31003C706F776572733E355F5F32003C636F756E743E355F5F33003C733E355F5F34003C693E355F5F350053797374656D2E436F6C6C656374696F6E732E47656E657269632E49456E756D657261746F723C53797374656D2E4F626A6563743E2E43757272656E740053797374656D2E436F6C6C656374696F6E732E49456E756D657261746F722E43757272656E7400446562756767657248696464656E4174747269627574650053797374656D2E546872656164696E6700546872656164006765745F43757272656E74546872656164006765745F4D616E616765645468726561644964004368617200537472696E670053706C697400496E743332004D61746800506F7700456D70747900436F6E636174006765745F4C656E67746800537562737472696E67004E6F74537570706F72746564457863657074696F6E00436F6D70696C657247656E6572617465644174747269627574650000000003200000000000C7D3D98C74FDDA4ABF2903EDC633808D0008B77A5C561934E08905000112090E0400010808060002011C100E032000010520010111150420010108816F010004005455794D6963726F736F66742E53716C5365727665722E5365727665722E446174614163636573734B696E642C2053797374656D2E446174612C2056657273696F6E3D322E302E302E302C2043756C747572653D6E65757472616C2C205075626C69634B6579546F6B656E3D623737613563353631393334653038390A446174614163636573730000000054557F4D6963726F736F66742E53716C5365727665722E5365727665722E53797374656D446174614163636573734B696E642C2053797374656D2E446174612C2056657273696F6E3D322E302E302E302C2043756C747572653D6E65757472616C2C205075626C69634B6579546F6B656E3D623737613563353631393334653038391053797374656D4461746141636365737300000000540E1146696C6C526F774D6574686F644E616D650746696C6C526F77540E0F5461626C65446566696E6974696F6E1A5065726D75746174696F6E206E7661726368617228343030302905151225011C05151229011C072000151229011C082000151229011300042000122D0320000202061C0320001C042000130002060802060E03061D0E03061D080328001C0401000000040000123903200008040701120C0620011D0E1D030500020D0D0D0600030E1C1C1C0520020E08080707040808081D0304070208080801000200000000000801000800000000001E01000100540216577261704E6F6E457863657074696F6E5468726F77730100000000000705BC5000000000020000007B000000202E000020100000525344531D0FE94AFF48A24EBCFEA0EEE9B8CD3602000000633A5C55736572735C5061756C2057686974655C446F63756D656E74735C56697375616C2053747564696F20323031305C50726F6A656374735C4461746162617365355C4461746162617365355C6F626A5C52656C656173655C44656D6F2E7064620000C42E00000000000000000000DE2E0000002000000000000000000000000000000000000000000000D02E0000000000000000000000005F436F72446C6C4D61696E006D73636F7265652E646C6C0000000000FF250020400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001000000018000080000000000000000000000000000001000100000030000080000000000000000000000000000001000000000048000000584000003C02000000000000000000003C0234000000560053005F00560045005200530049004F004E005F0049004E0046004F0000000000BD04EFFE00000100000000000000000000000000000000003F000000000000000400000002000000000000000000000000000000440000000100560061007200460069006C00650049006E0066006F00000000002400040000005400720061006E0073006C006100740069006F006E00000000000000B0049C010000010053007400720069006E006700460069006C00650049006E0066006F0000007801000001003000300030003000300034006200300000002C0002000100460069006C0065004400650073006300720069007000740069006F006E000000000020000000300008000100460069006C006500560065007200730069006F006E000000000030002E0030002E0030002E003000000034000900010049006E007400650072006E0061006C004E0061006D0065000000440065006D006F002E0064006C006C00000000002800020001004C006500670061006C0043006F0070007900720069006700680074000000200000003C00090001004F0072006900670069006E0061006C00460069006C0065006E0061006D0065000000440065006D006F002E0064006C006C0000000000340008000100500072006F006400750063007400560065007200730069006F006E00000030002E0030002E0030002E003000000038000800010041007300730065006D0062006C0079002000560065007200730069006F006E00000030002E0030002E0030002E003000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000C000000F03E00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000;
GO
CREATE FUNCTION dbo.Combinations
(
@ElementsCSV nvarchar (4000)
)
RETURNS TABLE
(
Combination nvarchar (4000) NULL
)
AS EXTERNAL NAME Demo.UserDefinedFunctions.Permute;
Exemple d'utilisation:
SELECT
f.Combination
FROM dbo.Combinations('A,B,C,D') AS f;
Sortie:
╔═════════════╗
║ Combination ║
╠═════════════╣
║ A ║
║ B ║
║ A,B ║
║ C ║
║ A,C ║
║ B,C ║
║ A,B,C ║
║ D ║
║ A,D ║
║ B,D ║
║ A,B,D ║
║ C,D ║
║ A,C,D ║
║ B,C,D ║
║ A,B,C,D ║
╚═════════════╝
En utilisant l'ensemble de 20 éléments du précédent:
DECLARE @Sample AS TABLE
(
item_id tinyint IDENTITY(1,1) PRIMARY KEY CLUSTERED,
item nvarchar(50) NOT NULL
);
INSERT @Sample
(item)
VALUES
(N'Ann'),
(N'Bob'),
(N'Charles'),
(N'Darren'),
(N'Eric'),
(N'Fred'),
(N'George'),
(N'Harry'),
(N'Ian'),
(N'John'),
(N'Keith'),
(N'Larry'),
(N'Mark'),
(N'Nathan'),
(N'Owen'),
(N'Paul'),
(N'Quentin'),
(N'Ryan'),
(N'Steve'),
(N'Terry');
Solution SQLCLR:
-- Create CSV input
DECLARE
@Elements nvarchar(4000) =
STUFF
(
(
SELECT ',' + s.item
FROM @Sample AS s
ORDER BY
s.item_id
FOR XML
PATH (''),
TYPE
).value('(./text())[1]', 'varchar(8000)'), 1, 1, ''
);
DECLARE
@bitbucket nvarchar(4000);
SELECT
@bitbucket = combination
FROM dbo.Combinations(@Elements);
Le temps d'exécution est de 2,5 secondes pour les 1 048 576 combinaisons sur mon ordinateur portable à DOP 1.
Création de l'entrée CSV:
Trouver les combinaisons:
Code source C #:
using System;
using System.Collections;
using Microsoft.SqlServer.Server;
public partial class UserDefinedFunctions
{
[SqlFunction
(
DataAccess=DataAccessKind.None,
SystemDataAccess=SystemDataAccessKind.None,
FillRowMethodName="FillRow",
TableDefinition="Permutation nvarchar(4000)"
)
]
public static IEnumerable Permute(string ElementsCSV)
{
// Split CSV
string[] elements = ElementsCSV.Split(new char[] { ',' });
// Highest integer needed
int count = (int)Math.Pow(2, elements.Length) - 1;
// Pre-computed array of 2^n values
int[] powers = new int[elements.Length];
for (int i = 0; i < powers.Length; i++)
{
powers[i] = (int)Math.Pow(2, i);
}
// Test integers
for (int i = 1; i <= count; i++)
{
// Reset output
string s = string.Empty;
// Test each bit that could be set
for (int bit = 0; bit < powers.Length && i >= powers[bit]; bit++)
{
if ((i & powers[bit]) == powers[bit])
{
// Add the element corresponding to the set bit
s += elements[bit] + ',';
}
}
// Return a row via enumeration
yield return s.Substring(0, s.Length - 1);
}
}
// Called by SQL Server to fetch a row
public static void FillRow(object o, out string Permutation)
{
Permutation = (string)o;
}
}
