More Maths...

For some unknown reason I seem to be getting a lot of SQL questions regarding maths functions.

An earlier post was concerned with Prime and Perfect numbers ( Post) but this time they have asked for Combinations and Permutations

Just quickly the formulaes for them are:
Combinations = N!/(K!*(N-K)!)
Permutations = N!/(N-K)!)
where N is the number of elements and K is the size of the permutation/combination. and ! is for factorial...

First thing to do is to create the Factorial function...
--Factorial function
CREATE FUNCTION dbo.Factorial
(@N INT)
RETURNS BIGINT
AS
BEGIN
DECLARE @Result BIGINT
SET @Result = 1
WHILE @N > 1
BEGIN
  SET @Result = @Result * @N
  SET @N = @N-1
END
RETURN @Result
END
GO
SELECT dbo.Factorial(3)
GO
The maximum allowed value on N in this function is 20. Anything greater than this will cause an overflow.
I leave it up to someone else to use real/float data types for bigger numbers...

Once we have this, constructing the Combination and Permutation functions are trivial....
--Combinations
CREATE FUNCTION dbo.Combinations
(@N INT,
@K INT)
RETURNS BIGINT
AS
BEGIN
RETURN dbo.Factorial(@N)/(dbo.Factorial(@K)*dbo.Factorial(@N-@K))
END
GO
SELECT dbo.Combinations(10,4)
GO

--Permutations
CREATE FUNCTION dbo.Permutations
(@N INT,
@K INT)
RETURNS BIGINT
AS
BEGIN
RETURN dbo.Factorial(@N)/dbo.Factorial(@N-@K)
END
GO
SELECT dbo.Permutations(10,4)

As a side note you can also calculate all of these functions using the Numbers table via the wacky variable assignment method....
Below is the mind boggling code for Permutations of 10_P_4... I'm still trying to understand it myself!
DECLARE @Result BIGINT
DECLARE @N INT, @K INT
SELECT @N = 10, @K = 4
SET @Result = 1
SELECT @Result = @Result * Number, @Result = @Result / CASE WHEN (@N-@K) >= Number THEN @Result ELSE 1 END
FROM Numbers
WHERE Number BETWEEN 1 AND @N
SELECT @Result

Print | posted on Tuesday, November 11, 2003 1:17 PM

Feedback

# re: More Maths...

left by Lavos at 11/11/2003 3:50 PM Gravatar
It's not exactly mind boggling once you have the math down. One of the first optimizations to make is to realize that N!/K! is equivalent to N*(n-1)*(n-2)*...*(k+1), which allows you to break out of calculating expensive factorials if K is fairly large compared to N. (Sort of like how (X+Y)/2 = ((X-Y)/2)+Y is useful for avoiding overflows while calculating a midpoint.) Basically, it is just removing anything below (@n-@k) by dividing it back out. Note that there is a bug in the statement since it is dividing by @Result instead of Number which makes it extremely dependant upon the order that rows are processed (thus forcing you to change it to Number or introduce an ORDER BY clause if you want to be safe.)

This means that your select statement for permutations could be written as:

SELECT @Result = @Result * Number
FROM Numbers
WHERE Number BETWEEN (@N-@K+1) AND @N


It's a little more complex for combinations since there is a second factorial to divide by. I'd suggest using a second select to divide it out instead of trying to introduce it into the same statement.

# re: More Maths...

left by DavidM at 11/11/2003 4:01 PM Gravatar
Thanks Lavos,

The maths is easy but trying to figure out how SQL Server manages the equation is the mind boggling part...

I like that solution, I can understand that easily enough....

Using the Numbers table is purely for giggles, we use the actual functions...

Substituting Number for @Result in the divide by causes an overflow..

# re: More Maths...

left by Lavos at 11/11/2003 4:49 PM Gravatar
It seems strange to me that it would cause an overflow (underflow?) When I'm less sleepy I'll have to take a look and see what's happening and what I'm missing. What is the datatype for the number column you are using?

It took me by surprise when I first saw the SELECT @Var=@Var+Op FROM .... construct, and I had to experiment with it to build my mental model of what was going on. I never thought of combining multiple operations into the same select statement though. I guess the best viewpoint is that it does the operations row by row as if it was a cursor/while loop except faster (in theory). Of course, this means it's dependant on the order that the rows are returned/processed which is why I mentioned the ORDER BY since it can cause the rows to be sorted in a specific way to be processed. [/educated guesses]

I thought about it being the select construct being the boggling part after I posted, but I thought everyone who had been around for a while had seen it posted in the forums (Where I first saw it. I think my initial reaction was "Holy @*&$%$!! does that even work?!?") by now.

I would still recomend implementing permutation/combination functions without using a factorial function, unless they just aren't called often enough with large numbers to affect anything :) (I can't seem to remember how I used to do combinations to reduce the number of overflows, but since it was procedural it might not be translatable)

# re: More Maths...

left by James Curran at 11/13/2003 1:21 AM Gravatar
And it does seem like the original author of the Numbers table version was going out of his way to be cryptic. The line:

@Result = @Result / CASE WHEN (@N-@K) >= Number THEN @Result ELSE 1 END

can be rewritten as:

@Result = CASE WHEN (@N-@K) >= Number THEN (@Result / @Result) ELSE (@Result / 1) END

and then simplifed to:

@Result = CASE WHEN (@N-@K) >= Number THEN (1) ELSE (@Result) END

From here, we can add in the first half of that line:

@Result = CASE WHEN (@N-@K) >= Number THEN (1) ELSE (@Result * Number) END

And then finally, reverse the sense of the case to the more logical:

@Result = CASE WHEN (@N-@K) < Number THEN (@Result * Number) ELSE (1) END

Getting from there to Lavos's SQL statement should be simple.


# re: More Maths...

left by DavidM at 11/13/2003 8:47 AM Gravatar
Thankyou James,

Cryptic? Not intentionally... As I have repeated, the use of the Numbers table for the calculation was just for giggles. Actually, I was pretty happy with it considering it was knocked up as an after thought in about 5 minutes.

You final statement is very elegant in comparison and far easy to comprehend that the multiply assignment method in my example.

Comments have been closed on this topic.