n! - let me count the ways

The other day I had an interesting discrete maths assignment question involving permutations - so I decided to codify it.

"How many ways can six people (Josh, Toby, CJ, Sam, Leo & Donna) sit, if Josh must sit to the left of Leo and to the right of Sam."

Now the astute reader will immediately recognize the answer to be 2 * (4! + 3!3!) = 120; but to be sure I wanted to double check this via C#. (I'm keen to redo this in F# too)

My solution was a quick hack, and is by no means "the best way" - but using linq it sure looks pretty.

class Program
{
    static IEnumerable<List<string>> Permutate(IEnumerable<string> people, 
                                               IEnumerable<string> current)
    {
        // Get remaining people and recurse
        foreach (var person in people.Where(x => current.Contains(x) == false))
            foreach (var result in Permutate(people, current.Concat(new string[] { person })))
                yield return result;
 
        if (current.Count() == people.Count())
            yield return current.ToList();
    }
   
    static void Main(string[] args)
    {
        string[] people = new string[] { "Josh", "Toby", "CJ", "Sam", "Leo", "Donna" };
  
        var result = Permutate(people, new string[] { }).ToList();
   
        // Josh sits to the left of Leo
        var Josh_Leo = result.Where(r =>
            r.FindIndex(x => x == "Josh") < r.FindIndex(x => x == "Leo"));
 
        // Josh sits to the right of Sam
        var Sam_Josh = Josh_Leo.Where(r =>
            r.FindIndex(x => x == "Sam") < r.FindIndex(x => x == "Josh"));
 
        var count = Sam_Josh.Count();
    }
}

This simple example shows why I'm a such fan of linq in C# - the pre-linq code for this certainly wouldn't be as eloquent.

Oh, and it also shows why I'm a fan of maths... it's much more efficient to just to calculate the factorials.

Update: Formatting code in a blog sure is a pain!