I ran into an interesting question from someone asking for all combinations of numbers. The thread was here, and it was confusing at first. However we started to understand what was being asked and eventually the person stopped, realizing that there were too many combinations.

However at one point there was this quote: I’m looking for combinations, not permutations since the order is unimportant.

That surprised me since I was thinking of things in the opposite manner. However when I read this article, it made sense: combinations and permutations

There is a table in the article that cleared it up. I’ve reproduced it here:

The left hand side is permutations, where order matters. The right hand side is combinations, of which there is only one. Order doesn’t matter so 1-2-3 is the same as 1-3-2, which is the same as 3-2-1 and all other orderings.

This shows mathematical semantics, but those are important in SQL because we do need to talk about combinations and permutations. A CROSS JOIN is normally how we handle combinations, which for three numbers are usually thought of as the way to handle all combinations, but I’m not sure how that works here.

If I create a quick table:

CREATE TABLE Combinations
( id int) GO INSERT Combinations select 1
INSERT Combinations select 2
INSERT Combinations select 3

and then perform a cross join:

SELECT a.id, b.id
 FROM Combinations a
   CROSS JOIN dbo.Combinations b

I get this:

id          id

———– ———–

1           1

2           1

3           1

1           2

2           2

3           2

1           3

2           3

3           3

Not all combinations. Even if I add in a third result:

SELECT a.id, b.id, c.id
 FROM Combinations a
   CROSS JOIN dbo.Combinations b
   CROSS JOIN dbo.Combinations c

id          id          id

———– ———– ———–

1           1           1

1           2           1

1           3           1

1           1           2

1           2           2

1           3           2

1           1           3

1           2           3

1           3           3

2           1           1

2           2           1

2           3           1

2           1           2

2           2           2

2           3           2

2           1           3

2           2           3

2           3           3

3           1           1

3           2           1

3           3           1

3           1           2

3           2           2

3           3           2

3           1           3

3           2           3

3           3           3

However, what about if I limit the result to remove duplicates:

SELECT a.id, b.id, c.id
 FROM Combinations a
   CROSS JOIN dbo.Combinations b
   CROSS JOIN dbo.Combinations c
WHERE a.id != b.id
AND b.id != c.id
AND a.id != c.id

That seems to work better:

id          id          id

———– ———– ———–

1           3           2

1           2           3

2           3           1

2           1           3

3           2           1

3           1           2

However that’s not a great solution. I’ve hardcoded the number of items, and it’s a cumbersome query. I think there has to be a better solution, but it’s probably one that’s beyond my T-SQL skills. If I look at 5 numbers, I get this:

SELECT a.id 'a', b.id 'b', c.id 'c', d.id 'd', e.id 'e' FROM Combinations a
   CROSS JOIN dbo.Combinations b
   CROSS JOIN dbo.Combinations c
   CROSS JOIN dbo.Combinations d
   CROSS JOIN dbo.Combinations e
WHERE a.id != b.id
AND a.id != c.id
AND a.id != d.id
AND a.id != e.id
AND b.id != c.id
AND b.id != d.id
AND b.id != e.id
AND c.id != d.id
AND c.id != e.id
AND d.id != e.id
ORDER BY a, b, c, d

I get 120 rows. If I look at 5!, that’s 120, so I think I’m correct. I’m not duplicating all the results, nor am I  going to look through them all, but they seem correct and ordered.

The thing this solution leaves out is the combinations that are less than the total number of items, as asked in the thread. So expanded combinations would be:

1

2

3

4

5

1 – 2

1 – 3

1 – 4

1 – 4

1 – 2 – 3

…

Not worth including those, but I think that would result in a series of UNION queries, which would get really ugly.

I’ll ask around, but if anyone has an interesting way to solve this that’s cleaner, I’d be interested.

Update

Someone posted this, which seems to work wonderfully:

DECLARE @s VARCHAR(25)

,@Iteration Int

SET @s = ‘ABC’;

SET @Iteration = LEN(@s);

WITH E1(N) AS ( –=== Create Ten 1′s

SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 –10

),

cteTally(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT N)) FROM E1

),CteCombos AS (

SELECT CAST(SUBSTRING(@s, N, 1) AS VARCHAR(25)) AS Token,

CAST(‘.’+CAST(N AS CHAR(1))+’.’ AS VARCHAR(52)) AS Permutation,

CAST(1 AS INT) AS Iteration

FROM cteTally WHERE N <= @Iteration

UNION ALL

SELECT CAST(Token+SUBSTRING(@s, N, 1) AS VARCHAR(25)) AS Token,

CAST(Permutation+CAST(N AS CHAR(1))+’.’ AS VARCHAR(52)) AS

Permutation,

s.Iteration + 1 AS Iteration

FROM CteCombos s

INNER JOIN cteTally n

ON s.Permutation NOT LIKE ‘%.’+CAST(N AS CHAR(1))+’.%’

AND s.Iteration < @Iteration

AND N <= @Iteration

)

SELECT Token,Permutation,Iteration

FROM CteCombos

WHERE Iteration = @Iteration

ORDER BY Permutation

If you alter the variable (abc) to the number of items you need, so “abcde” for 5, this returns the combinations.

Filed under: Blog Tagged: syndicated, T-SQL