7

Given the following SQL Server table with a single char(1) column:

Value
------
'1'
'2'
'3'

How do I obtain the following results in T-SQL?

Result
------
'1+2+3'
'1+3+2'
'2+1+3'
'2+3+1'
'3+2+1'
'3+1+2'

This needs to be dynamic too, so if my table only holds rows '1' and '2' I'd expect:

Result
------
'1+2'
'2+1'

It seems like I should be able to use CROSS JOIN to do this, but since I don't know how many rows there will be ahead of time, I'm not sure how many times to CROSS JOIN back on myself..?

SELECT a.Value + '+' + b.Value
FROM MyTable a
CROSS JOIN MyTable b
WHERE a.Value <> b.Value

There will always be less than 10 (and really more like 1-3) rows at any given time. Can I do this on-the-fly in SQL Server?

Edit: ideally, I'd like this to happen in a single stored proc, but if I have to use another proc or some user defined functions to pull this off I'm fine with that.

Dave Ziegler
  • 1,737
  • 3
  • 19
  • 36

2 Answers2

12

This SQL will compute the permutations without repetitions:

WITH recurse(Result, Depth) AS
(
    SELECT CAST(Value AS VarChar(100)), 1
    FROM MyTable

    UNION ALL

    SELECT CAST(r.Result + '+' + a.Value AS VarChar(100)), r.Depth + 1
    FROM MyTable a
    INNER JOIN recurse r
    ON CHARINDEX(a.Value, r.Result) = 0
)

SELECT Result
FROM recurse
WHERE Depth = (SELECT COUNT(*) FROM MyTable)
ORDER BY Result

If MyTable contains 9 rows, it will take some time to compute, but it will return 362,880 rows.

Update with explanation:

The WITH statement is used to define a recursive common table expression. In effect, the WITH statement is looping multiple times performing a UNION until the recursion is finished.

The first part of SQL sets the starting records. Assuming 3 rows named 'A', 'B', and 'C' in MyTable, this will generate these rows:

    Result     Depth
    ------     -----
    A          1
    B          1
    C          1

Then the next block of SQL performs the first level of recursion:

    SELECT CAST(r.Result + '+' + a.Value AS VarChar(100)), r.Depth + 1
    FROM MyTable a
    INNER JOIN recurse r
    ON CHARINDEX(a.Value, r.Result) = 0

This takes all of the records generated so far (which will be in the recurse table) and joins them to all of the records in MyTable again. The ON clause filters the list of records in MyTable to only return the ones that do not exist already in this row's permutation. This would result in these rows:

    Result     Depth
    ------     -----
    A          1
    B          1
    C          1
    A+B        2
    A+C        2
    B+A        2
    B+C        2
    C+A        2
    C+B        2

Then the recursion loops again giving these rows:

    Result     Depth
    ------     -----
    A          1
    B          1
    C          1
    A+B        2
    A+C        2
    B+A        2
    B+C        2
    C+A        2
    C+B        2
    A+B+C      3
    A+C+B      3
    B+A+C      3
    B+C+A      3
    C+A+B      3
    C+B+A      3

At this point, the recursion stops because the UNION does not create any more rows because the CHARINDEX will always be 0.

The last SQL filters all of the resulting rows where the computed Depth column matches the # of records in MyTable. This throws out all of the rows except for the ones generated by the last depth of recursion. So the final result will be these rows:

    Result
    ------
    A+B+C
    A+C+B
    B+A+C
    B+C+A
    C+A+B
    C+B+A
David
  • 34,223
  • 3
  • 62
  • 80
  • 1
    Wow this is way cool. How the heck does it work? Looks like magic. – Yuriy Galanter Sep 17 '13 at 20:25
  • I'm checking this out now, it seems to be doing what I want :) I'll report back shortly... – Dave Ziegler Sep 17 '13 at 20:26
  • I was just sqlfiddling this... nice one :) – Eli Gassert Sep 17 '13 at 20:27
  • Seriously @David could you please update the answer with explanation of this voodoo? – Yuriy Galanter Sep 17 '13 at 20:52
  • It's actually pretty simple (and simpler than it could have been because the values are only 1 character long). First, you get all the values in the table, then recursively concatenate the previous iteration with all the values in the table, as long as those values aren't already in the string (the `CHARINDEX` bit). So, it'd look like `1`, `1+2`, `1+2+3`, etc. Finally, you filter to the "right" combinations by getting the ones where the `Depth` equals the number of elements you started with. – bhamby Sep 17 '13 at 21:07
  • 1
    I've added some examples to go along with @bhamby's explanation. – David Sep 18 '13 at 00:33
  • The best introduction to recursive CTEs I have seen. Thanks a bunch @David! – Der U Sep 18 '13 at 12:57
2

You can do this with a recursive CTE:

with t as (
      select 'a' as value union all
      select 'b' union all
      select 'c'
     ),
     const as (select count(*) as cnt from t),
     cte as (
      select cast(value as varchar(max)) as value, 1 as level
      from t
      union all
      select cte.value + '+' + t.value, 1 + level
      from cte join
           t 
           on '+'+cte.value+'+' not like '%+'+t.value+'+%' cross join
           const
      where level <= const.cnt
     )
select cte.value
from cte cross join
     const
where level = const.cnt;
Gordon Linoff
  • 1,242,037
  • 58
  • 646
  • 786