// This software is released under the MIT license
// https://opensource.org/licenses/MIT
//
// gmail me at benjaminaburns
//
// Note: 
// Visual Studio users, be sure to add this to the app.config
//
// <runtime>
//		<gcAllowVeryLargeObjects enabled = "true" />
// </ runtime >
//

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PartitionCount
{
    class Program
    {
        static void Main(string[] args)
        {
            // This program counts the number of ways {1, ..., n} elements can
            // be divided into sum-free sets across n or fewer partitions.
            //
            // Order doesn't matter, so { 1|2 } is the same as { 2|1 }. Additionally,
            // empty partitions are ignored so  { 1|{} } = { {}|1 } = { 1 }.
            //
            // Each successive generation can be created by iterating over the previous
            // generation and inserting n into each partition if allowed, and also
            // appending n to the end as its own partition. This program starts with 
            // the empty set which causes a special case of a duplicate for n=1 when
            // following the above algorithm; this special case is handled in code.
            // For larger values of n there won't be duplicates.
            //
            // examples, where "|" is a partition divider
            // a(1): { 1 }
            // a(2): { 1|2 }
            // a(3): { 1,3|2 }, { 1|2,3 }, { 1|2|3 }
            // a(4): { 1,3|2|4 }, { 1,4|2,3 }, { 1|2,3|4 }, { 1,4|2|3 }, { 1|2|3,4 }, { 1|2|3|4 }

            // Informally, the universe is a list
            //   containing collections
            //     of partitions
            //       of integers.
            var universe = new List<List<List<int>>>();

            // new_universe is built based on the existing
            // universe. This is done to avoiding modifying the universe object
            // in place. At the end of every iteration, the current universe
            // is discarded and replaced with new_universe.
            List<List<List<int>>> new_universe = null;

            // Start with the empty set, will build up from here starting with 1.
            var starting_partition = new List<int>();
            var starting_collection = new List<List<int>>();
            starting_collection.Add(starting_partition);
            universe.Add(starting_collection);

            // max_n = 14 -> on VS2017 uses abount 3GB ram, max_n = 15 uses around 34.
            int max_n = 15;
            for (int n=1; n<max_n; n++)
            {
                new_universe = new List<List<List<int>>>();

                int universe_length = universe.Count();
                for (int c = 0; c < universe_length; c++)
                {
                    var collection = universe[c];
                    int collection_length = collection.Count();

                    // append n to each existing partition, if possible
                    for (int p=0; p<collection_length; p++)
                    {
                        var new_collection = new List<List<int>>();
                        var partition = collection[p];
                        if (IsSumFreeWith(partition, n))
                        {
                            // new List constructor just points to the argument, it won't duplicate
                            // it. Therefore, force instantiation of a new list in memory by
                            // calling ToArray().ToList().
                            var new_partition = new List<int>(partition.ToArray().ToList());
                            new_partition.Add(n);

                            for (int p_copy = 0; p_copy < collection_length; p_copy++)
                            {
                                // This will preserve the order of the existing collection.
                                if (p_copy == p)
                                {
                                    new_collection.Add(new_partition);
                                }
                                else
                                {
                                    new_collection.Add(new List<int>(collection[p_copy].ToArray().ToList()));
                                }
                            }

                            new_universe.Add(new_collection);
                        }
                    }

                    // Append a new partition consisting only of n.
                    // (empty for loop to avoid variable naming scope conflict with above)
                    for (;;)
                    {
                        // special case
                        if (n == 1)
                        {
                            break;
                        }

                        var new_collection = new List<List<int>>();
                        var new_partition = new List<int>();
                        new_partition.Add(n);

                        for (int p_copy = 0; p_copy < collection_length; p_copy++)
                        {
                            new_collection.Add(new List<int>(collection[p_copy].ToArray().ToList()));
                        }
                        new_collection.Add(new_partition);

                        new_universe.Add(new_collection);
                        break;
                    }
                }

                universe = new_universe;

                Console.WriteLine(universe.Count());
            }
        }

        // Checks whether n can be added to the given sum-free set.
        // This is a naive implementation; this program assumes memory will
        // be the limiting factor before computation time is.
        public static bool IsSumFreeWith(List<int> arr, int n)
        {
            int len = arr.Count();
            for (int i=0; i<len; i++)
            {
                for (int j=i; j<len; j++)
                {
                    if (arr[i] + arr[j] == n)
                    {
                        return false;
                    }
                }
            }

            return true;
        }
    }
}