factorial of n numbers using c# lambda..?

Question

Hi,

I just started playing with lambdas and Linq expression for self learning. I took the simple factorial problem for this. with the little complex scenario where find the factorial for given n numbers (witout using recursive loops).

Below the code i tried. But this is not working.

public void FindFactorial(int range)
{

    var res = Enumerable.Range(1, range).Select(x => Enumerable.Range(0, x).Where(y => (y > 1)).Select(y => y * (y-1)));            
    foreach (var outt in res)
        Console.WriteLine(outt.ToString());

}

this is the procedure i used

• loop through the numbers 1 to n -- Enumerable.Range(1, range).
• select each number x and again loop them upto x times (instead of recursion)
• and select the numbers Where(y => (y > 1)) greater than 1 and multiply that with (y-1)

i know i messed up somewhere. can someone tell me whats wrong and any other possible solution.

EDIT:

i am going to let this thread open for some time... since this is my initial steps towards lambda.. i found all the answers very useful and informative.. And its going to be fun and great learning seeing the differnt ways of approaching this problem.

Cheers

Ramesh Vel

Answer 1

Currently there's no recursion - that's the problem. You're just taking a sequence of numbers, and projecting each number to "itself * itself-1".

The simple and inefficient way of writing a factorial function is:

Func<int, int> factorial = null; // Just so we can refer to it
factorial = x => x <= 1 ? 1 : x * factorial(x-1);

for (int i = 1; i <= range; i++)
{
    Console.WriteLine(factorial(i));
}

Typically you then get into memoization to avoid having to repeatedly calculate the same thing. You might like to read Wes Dyer's blog post on this sort of thing.

Answer 2

Just to continue on Jon's answer, here's how you can memoize the factorial function so that you don't recompute everything at each step :

public Func<T, TResult> Memoize<T, TResult>(Func<T, TResult> func)
{
    Dictionary<T, TResult> _resultsCache = new Dictionary<T, TResult>();
 return (arg) =>
 {
     TResult result;
     if (!_resultsCache.TryGetValue(arg, out result))
  {
   result = func(arg);
   _resultsCache.Add(arg, result);
  }
  return result;
 };
}

...

Func<int, int> factorial = null; // Just so we can refer to it
factorial = x => x <= 1 ? 1 : x * factorial(x-1);
var factorialMemoized = Memoize(factorial);
var res = Enumerable.Range(1, 10).Select(x => factorialMemoized(x));
foreach (var outt in res)
    Console.WriteLine(outt.ToString());

EDIT: actually the code above is not correct, because factorial calls factorial, not factorialMemoized. Here's a better version :

Func<int, int> factorial = null; // Just so we can refer to it
Func<int, int> factorialMemoized = null;
factorial = x => x <= 1 ? 1 : x * factorialMemoized(x-1);
factorialMemoized = Memoize(factorial);
var res = Enumerable.Range(1, 10).Select(x => factorialMemoized(x));
foreach (var outt in res)
    Console.WriteLine(outt.ToString());

With that code, factorial is called 10 times, against 55 times for the previous version

Answer 3

I tried to come up with something resembling F#'s scan function, but failed since my LINQ isn't very strong yet.

Here's my monstrosity:

//this is similar to the folowing F# code: 
//let result = [1..10] |> List.scan (fun acc n -> acc*n) 1

var result = 
    Enumerable.Range(1, 10)
        .Aggregate(new List<int>(new[] { 1 }),
                    (acc, i) => {
                            acc.Add(i * acc.Last());
                            return acc;
                        }
                   );

foreach(var num in result) Console.WriteLine("{0}",num);

If anyone knows if there actually is an equivalent of F#'s scan function in LINQ that I missed, I'd be very interested.

Answer 4

Simple although no recursion here:

public static int Factorial(this int count)
{
        return count == 0
                   ? 1
                   : Enumerable.Range(1, count).Aggregate((i, j) => i*j);
}

3.Factorial() == 6