/* Created for this challenge: https://www.sololearn.com/post/20397 Solve the problem in any language? Among the several path breaking contributions to Number theory by the famous Indian mathematician Srinivasa Ramanujan, his contribution to partitions is extensive and deep. A partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 can be expressed as a sum of positive integers in the following ways: 1+1+1+1, 1+1+2, 1+3, 2+2, 4. Of these, only 1+3 and 4 use non repeating summands. Partitions using non repeating summands are called distinct partitions of n. There is no general formula for the number of partitions of an integer n and it is known that the partitions grow rapidly with n. A k-distinct-partition of a number n is a set of k distinct positive integers that add up to n. For example, 3-distinct partitions of 10 are 1+2+7, 1+3+6,1+4+5 and 2+3+5 objective is to count all k-distinct partitions of a num That have at least two perfect squares. Explanation Example 1 Input 10, 3 Output 1 Explanation: The input asks for 3-distinct-partitions of 10. There are 4 of them (1+2+7, 1+3+6, 1+4+5 and 2+3+5). Of these, only 1 has at least two perfect squares in the partition (1+4+5). Example 2 Input 12, 3 Output 2 */ #include #include // Allocate a class to provide data access similar // to Kotlin's nested functions. class Partition { // Private data storage of the number in process, // the partition size, the list of distinct // partitions, and the working list of distinct // numbers. private: int number; int partitions; std::list> result; std::list array; // Methods used in process to create the // list of distinct partitions, find the // next distinct number set, and sum the // current number set. void distinct(); void find(int index); int sum(); // Make constructor and process public. The // constructor just stores the arguments so // process can do the work of counting distinct // partitions with multiple perfect squares. public: Partition(int number, int partitions); int process(); }; // Partition // Create the class. Partition::Partition(int number, int partitions) { this->number = number; this->partitions = partitions; } // Partition // Create a list of distinct partitions for the // requested number with the requested values in // each partition. void Partition::distinct() { // Allocate an empty resultant list and an array // to hold the current working partition. Find // all of the distinctive partitions adding them // to the list. result = std::list>(); array = std::list(); for (int index = 1; index <= partitions; index++) array.push_back(index); find(partitions-1); } // distinct // Recursive function to find each distinctive // partition. void Partition::find(int index) { // Position the iterator correctly. std::list::iterator it = array.begin(); for (int position = 0; position < index; position++) it++; // Set the minimum to one or one greater than // the preceeding array element. int min = (index == 0)?1:*prev(it)+1; // Set the maximum to the number or one less // than the next array element. int max = (index == partitions-1)?number: *next(it)-1; // For each possible value, try it. If we // have more elements to process recurse_ // to set them. Otherwise, we have a complete // distinctive array of values so if the // sum to our number, we can add it to the // resultant list. for (int value = min; value <= max; value++) { *it = value; if (index > 0) find(index-1); else if (sum() == number) { std::list copy = array; result.push_back(copy); } // it } // for // Reset this element to the minimum. *it = min; } // find // Check the distinct partitions for having two or // more squares returning how many passed the test. int Partition::process() { // Get some squares to check for, default the // count to zero, and get the distinctive // partitions. int maxSquares = number/3; std::list squares = std::list(); for (int index = 1; index <= maxSquares; index++) squares.push_back(index*index); int count = 0; distinct(); // For each partition in the list, default the // square test to zero and check our squares. std::list>::iterator itResult = result.begin(); while (itResult != result.end()) { int test = 0; std::list::iterator itSquares = squares.begin(); while (itSquares != squares.end() && test < 2) { // If this square is in the partition, // increment the count of them and see if // we got two. If so, this partition counts // so increment the count and skip to the // next one. std::list::iterator itList = (*itResult).begin(); while (itList != (*itResult).end()) { if (*itSquares == *itList) if (++test == 2) { count++; break; } // if itList++; } // while itSquares++; } // while itResult++; } // while return count; } // process // Sum the elements in our working partition. int Partition::sum() { int sum = 0; std::list::iterator it = array.begin(); while (it != array.end()) { sum += *it; it++; } // while return sum; } // sum // Process the challenge. int main() { // Declare the number & size of the partitions // and attempt to read them. If we got valid // values, process them. int number = -1, partitions = -1; std::cin >> number >> partitions; if (number > 0 && partitions > 0) { Partition partition = Partition(number, partitions); int result = partition.process(); std::cout << "(" << number << ", " << partitions << ")=" << result << std::endl; // Otherwise, complain and process the defaults. } else { std::cout << "Bad input, using defaults!" << std::endl; int tests[7][2] = {{10, 3}, {12, 3}, {20, 1}, {20, 2}, {20, 3}, {20, 4}, {20, 5}}; for (int index = 0; index < 7; index++) { Partition partition = Partition( tests[index][0], tests[index][1]); int result = partition.process(); std::cout << "(" << tests[index][0] << ", " << tests[index][1] << ")=" << result << std::endl; } // for } // if return 0; } // main

summands ch