Monday, November 5, 2007

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!

No comments: