Previous Entry Next Entry→

September 22, 2005

I haven't used visual informatics in so long, I feel like I starting to go blind!  Although, I did take some time out to viddy, and oh, baby--the memories of places and times correlate strongly with some of these machines.

How about first getting the recursive function for integer partitions working and then look into some visuals?  Plan?  My first implementation is very simple:

 /// recursive call F(n,k) = F(n-k,k) + F(n,k+1) #include using namespace std; // Recursive function int f(int, int); void main() { cout << "****************************************************\n"      << "* Compute the number of integer partitions         *\n"      << "* of a number N by the recursive call              *\n"      << "* F(n,k) = F(n-k,k) + F(n,k+1).                    *\n"      << "* For instance, F(5,1) = F(4,1) + F(5,2) =         *\n"      << "* = (F(3,1) + F(4,2)) + (F(3,2) + F(5,3)) =        *\n"      << "* = (F(2,1) + F(3,2) + F(2,2) + F(4,3)) + (1 + 1)  *\n"      << "* = 2 + 1 + 1 + 1 + 2                              *\n"      << "* = 7                                              *\n"      << "****************************************************\n";      int n=1;      while(n>0) {         cout << "\n\n Enter the integer whose partition value will be computed: ";          cin >> n;         cout << " Partiions(" << n << ") = " << f(n,1);       } } // end main int f(int n, int k) {      if(k>n) return 0;      else if(k>n/2) return 1;      else return f(n-k,k) + f(n,k+1); }

The output is shown below.   As is characteristic of these recursive functions, the time to compute the partitions of 100 was rather long, and this seems to be close to the limit of what this code can do.

 **************************************************** * Compute the number of integer partitions         * * of a number N by the recursive call              * * F(n,k) = F(n-k,k) + F(n,k+1).                    * * For instance, F(5,1) = F(4,1) + F(5,2) =         * * = (F(3,1) + F(4,2)) + (F(3,2) + F(5,3)) =        * * = (F(2,1) + F(3,2) + F(2,2) + F(4,3)) + (1 + 1)  * * = 2 + 1 + 1 + 1 + 2                              * * = 7                                              * **************************************************** Enter the integer whose partition value will be computed: 9 Partiions(9) = 30 Enter the integer whose partition value will be computed: 11 Partiions(11) = 56 Enter the integer whose partition value will be computed: 15 Partiions(15) = 176 Enter the integer whose partition value will be computed: 25 Partiions(25) = 1958 Enter the integer whose partition value will be computed: 100 Partiions(100) = 190569292 Enter the integer whose partition value will be computed:

http://www.main.cz/colors/color_names.htm