// 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; } } }