SQL query for combinations without repetition

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