## More Maths...

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

## Feedback

## # re: More Maths...

left by Lavos at 11/11/2003 3:50 PMThis 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 PMThe 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 PMIt 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@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 AMCryptic? 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.