Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I need a query which can be used in (or as) a function and retrieves all combinations of n values. And I need all combinations of length k where k = 1..n.

Extended sample input and result so input has 3 values instead of 2 - however, number of input values may vary from 1 to n.

Example:

Input: table with values in one column in multiple rows

Value  (nvarchar(500))
------
Ann
John
Mark

Output#1: table with values concatenated in one column

    Ann
    John
    Mark
    Ann,John
    John,Ann
    Ann,Mark
    Ann,John,Mark
share|improve this question
1  
@Alex: Similar but not the same question. I've edited this for preciseness. –  ypercube Dec 2 '12 at 18:16
1  
@Alex Similar. Even if it were a duplicate, the answers there are not worth the bits to display them on screen. The accepted solution says "set-based" then proceeds to loop... –  孔夫子 Dec 2 '12 at 21:47

1 Answer 1

up vote 20 down vote accepted

For relatively small values of n (20 in this example), you can use a method that exploits the fact that the natural integers are combinations of bits.

T-SQL Solution

Sample data:

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;

Output sample:

╔════════════════════════╗
║      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 ║
║ ...                    ║
╚════════════════════════╝

Execution plan:

Execution plan

It takes 41 seconds to write the 1,048,576 combinations to a variable on my laptop. With forced parallelism, I was able to drop the execution time at DOP 8 to 13 seconds.

If you need a Numbers table, this is a quick way to produce one:

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);

SQLCLR solution

A much more efficient implementation is possible in SQLCLR (SQL Server 2005 onward):

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;

Example usage:

SELECT 
    f.Combination
FROM dbo.Combinations('A,B,C,D') AS f;

Output:

╔═════════════╗
║ 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     ║
╚═════════════╝

Using the 20-element set from earlier:

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');

SQLCLR solution:

-- 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);

Execution time is 2.5 seconds for the 1,048,576 combinations on my laptop at DOP 1.

Creating the CSV input:

CSV Input Plan

Finding the combinations:

SQLCLR Function Plan

C# Source Code:

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;
    }
}
share|improve this answer
2  
You're not sorting the singles before the doubles etc as in OP's output. =p Just kidding +1 as usual for a brilliantly complete answer. –  孔夫子 Dec 2 '12 at 11:35
    
Yoink! Thanks Paul, I have a "10! combination without repetition" requirement, and now using your T-SQL version. It hasn't quite sunk in yet how the bitwise&, the order by, and the for_xml are working exactly. I will spend the next few months trying to understand it no doubt –  Davos Aug 6 at 8:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.