# SQL query for combinations without repetition

I need a function that can generate all possible combinations of a given set of n values. For each combination, the function should also generate all combinations of length k, where k ranges from 1 to n.

For example, if the input is a table with three values in one column, then the function should generate all possible combinations of the three values, as well as all possible combinations of length 1, 2, and 3.

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,Mark
Ann,Mark
Ann,John,Mark

``````

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:

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]
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:

Finding the combinations:

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;
}
}
``````