Earlier this month we had a TSQL Tuesday on the topic of CTEs. I bailed on my submission because I already posted some CTE examples and was bone dry on what I could write about.
Later I saw a request for some help on creating combinations and permutations from TSQL. I thought about this request and finally came up with the idea to use CTEs to do it. The idea came about based on seeing multiple suggestions in that thread and then combining some of the pieces together. Though not a suggestion, per-se, but seeing in the code submitted that a factorial was being used along with the sum of all integers from 1 to the given integer (or summation), I decided I would incorporate that into my solution.
I thus set out to create a solution that would use a CTE to generate those permutations, the summation, and the factorial. In this article I will just be focusing on how I came to produce the factorial and summation using a little bit of Recursive CTE. Also, we will see an alternative solution to calculating the summation. For help in setting up the structure of a recursive CTE, you may want to refer to this article.
Here is the script first, and then I will explain later.
[codesyntax lang=”tsql”]
DECLARE @FactNum INT
SET @FactNum = '50';
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
),
E2(N) AS (SELECT 1 FROM E1 a, E1 b), --100
E4(N) AS (SELECT 1 FROM E2 a, E2 b), --10,000
cteTally(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT N)) FROM E4
),CTEMathN(N,Factorial,Aggreg,Iteration) AS (
SELECT N
,CAST(1 AS NUMERIC(38,0)) AS Factorial
,N AS Aggreg
,CAST(1 AS INT) AS Iteration
FROM ctetally
WHERE N <= @FactNum
AND @FactNum <= 33
UNION ALL
SELECT t.N
,t.n * CAST(f1.Factorial AS NUMERIC(38,0)) AS Factorial
,t.N + Aggreg AS Aggreg
,CAST(f1.Iteration + 1 AS INT) AS Iteration
FROM CTEMathN f1
INNER JOIN cteTally T
ON t.n = f1.n +1
AND t.N <= @FactNum
),CTEMathF(N,Factorial,Aggreg,Iteration) AS (
SELECT N
,CAST(1 AS FLOAT) AS Factorial
,N AS Aggreg
,CAST(1 AS INT) AS Iteration
FROM ctetally
WHERE N <= @FactNum
AND @FactNum > 33
UNION ALL
SELECT t.N
,t.n * CAST(f1.Factorial AS FLOAT) AS Factorial
,t.N + Aggreg AS Aggreg
,CAST(f1.Iteration + 1 AS INT) AS Iteration
FROM CTEMathF f1
INNER JOIN cteTally T
ON t.n = f1.n +1
AND t.N <= @FactNum
)
SELECT ISNULL(CAST(CN.N AS VARCHAR(100)),CAST(CF.N AS VARCHAR(100))) AS N
,ISNULL(CAST(CN.Factorial AS VARCHAR(100)),CAST(CF.Factorial AS VARCHAR(100))) AS Factorial
,ISNULL(CAST(CN.Aggreg AS VARCHAR(100)),CAST(CF.Aggreg AS VARCHAR(100))) AS Aggreg
FROM CTEMathN CN
FULL OUTER JOIN CTEMathF CF
ON CN.N = CF.N
WHERE ISNULL(CN.Iteration,CF.Iteration) = @FactNum[/codesyntax]
As you can see, I am using several CTEs in this script. The first group of CTEs is to create a Dynamic Tally (Numbers) table. The last two CTEs are performing the same thing but with a bit of filtering applied. When you look at them, you should note that the first one is Casting the Factorial to a Numeric data type. The last CTE is casting the Factorial to a FLOAT data type. This isn’t necessarily required but more of an aesthetic for myself. So any number greater than 33 will use the FLOAT data type and anything less than 34 will use the numeric data type.
The FLOAT data type will support those smaller numbers – that’s not an issue. The Numeric data type will not support the larger values (it is limited to 38 characters). We start running into arithmetic overflow at 34! and must use the FLOAT at that point. The problem is that I prefer to avoid the overflow style of displaying the numbers except when necessary. For simplicity sake, you could eliminate the filtering between the CTEs and simply use the FLOAT across the board.
Since I am trying to filter between the two and create a single row result set, I also have a second issue that is created by this code. That issue is resolved and seen when performing the final select from the CTEs. If the query requires the use of FLOAT, I will get an error message with an arithmetic overflow again unless I Convert the Numeric and Float results into something that is compatible between the two. I chose to use VarChar(100) in this case.
Note, also, that I am using a FULL OUTER Join in the final query. This is due to the fact that I will see results in either the CTEMathN or CTEMathF CTE but not both.
Now down into the nitty gritty. Let’s look at CTEMathN to see how we are getting the factorial and the summation.
[codesyntax lang=”tsql”]
SELECT N ,CAST(1 AS NUMERIC(38,0)) AS Factorial ,N AS Aggreg ,CAST(1 AS INT) AS Iteration FROM ctetally WHERE N <= @FactNum AND @FactNum <= 33 UNION ALL SELECT t.N ,t.n * CAST(f1.Factorial AS NUMERIC(38,0)) AS Factorial ,t.N + Aggreg AS Aggreg ,CAST(f1.Iteration + 1 AS INT) AS Iteration FROM CTEMathN f1 INNER JOIN cteTally T ON t.n = f1.n +1 AND t.N <= @FactNum
[/codesyntax]
First we have the required anchor definition. Second we have the recursion definition joined by the Union All and referencing the same CTE where both of these pieces reside.
The factorial is easy enough. Since a Factorial is n! or n(n-1) we can multiply n by the previous n in the sequence. We can get both of those values through our join statement where we join back out to the Tally CTE and showing an increment in the number (here I am join CTETally.n to CTEMathN +1). This ensures we will move through the record set (or recurse).
The same principle applies for the summation. We add each number in the sequence from 1 to n to retrieve our result. So, much the same as the factorial, I add n to the previous value of n and proceed from there through the record set.
Note also that I threw an additional limiting factor on the where clause. I want to make sure that I do not try to recurse through a record set that includes numbers outside of my range.
Now, since I only really care about the factorial and summation for the number I inserted in the variable at the beginning, I want to make sure that I have a filter added to the final select clause. Here is that final filter…
[codesyntax lang=”tsql”]
WHERE ISNULL(CN.Iteration,CF.Iteration) = @FactNum
[/codesyntax]
This enforces a single record will be returned by selecting only the last iteration. Iteration is another column in the CTEs that is used during our recursion process. The iteration column just increments by a value of one with each pass.
Pretty easy eh?
Now, if all you need is a summation and it is not used to control result sets (like mine will be in the next bit where we discuss permutations), then you could rip out the aggregation stuff and just use this in the final select statement…
[codesyntax lang=”tsql”]
((@FactNum * @FactNum)+ @FactNum )/ 2 AS Summation
[/codesyntax]
That would be in place of this bit…
[codesyntax lang=”tsql”]
ISNULL(CAST(CN.Aggreg AS VARCHAR(100)),CAST(CF.Aggreg AS VARCHAR(100))) AS Aggreg
[/codesyntax]
Have fun with it!!
