Problem 32 - Pandigital products

Problem: 

Please find the problem here.

Solution:

My current solution is kind of slow - it runs through all permutations and all possible splits to check for the product formula, and when it does accumulate the results, it is that simple.

It would be great if we could speed this up using some more constraints, but for now, this is good enough to produce and answer.

It would be an interesting detour to discuss the permutation generating algorithm. In some sense it is simple, pick the head, recursively compute the permutation of remaining elements, and concat with the head. Note that we could have been faster if we optimize the permutation method to reuse the same buffer instead of creating new list for each recursive result!

Code:

namespace Euler
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Numerics;

    internal static partial class Program
    {
        public static IEnumerable<IEnumerable<T>> Permutations<T>(IEnumerable<T> available)
        {
            List<T> availableList = available.ToList();
            return Permutations(availableList.Select(t => Pair<bool, T>.Create(true, t)).ToArray(), availableList.Count);
        }

        private static IEnumerable<IEnumerable<T>> Permutations<T>(Pair<bool, T>[] available, int count)
        {
            if (count == 0)
            {
                yield return new List<T> { };
            }

            for (int i = 0; i < available.Length; i++)
            {
                if (available[i].Item1)
                {
                    available[i].Item1 = false;
                    foreach (IEnumerable<T> recursiveResult in Permutations(available, count - 1))
                    {
                        yield return new List<T> { available[i].Item2 }.Concat(recursiveResult);
                    }

                    available[i].Item1 = true;
                }
            }
        }

        private class Pair<T, U>
        {
            public static Pair<T, U> Create(T item1, U item2)
            {
                return new Pair<T, U>(item1, item2);
            }

            private Pair(T item1, U item2)
            {
                this.Item1 = item1;
                this.Item2 = item2;
            }

            public T Item1 { get; set; }

            public U Item2 { get; set; }

        }

        public static void Problem032()
        {
            HashSet<int> results = new HashSet<int>();
            foreach (var permutation in Permutations(Enumerable.Range(1, 9).ToArray()))
            {
                // Break down the permutation into list of different partitions and check product formula
                for (int firstPart = 1; firstPart < 9; firstPart++)
                {
                    for (int secondPart = 1; secondPart < 9; secondPart++)
                    {
                        int thirdPart = 9 - firstPart - secondPart;
                        if (thirdPart > 0)
                        {
                            string permutationString = permutation.Aggregate("", (s, x) => s + x);
                            int firstPartValue = int.Parse(permutationString.Substring(0, firstPart));
                            int secondPartValue = int.Parse(permutationString.Substring(firstPart, secondPart));
                            int thirdPartValue = int.Parse(permutationString.Substring(9 - thirdPart));
                            if (firstPartValue == secondPartValue * thirdPartValue)
                            {
                                results.Add(firstPartValue);
                                //Console.WriteLine("{0} = {1} x {2}", firstPartValue, secondPartValue, thirdPartValue);
                            }
                        }
                    }
                }
            }
            Console.WriteLine(results.Aggregate((x, y) => x + y));
        }
    }
}