Merging of Companies

Suppose we have N companies, and we want to eventually merge them into
one big company. How many ways are there to merge?

Select any two companies and merge them, now we are left with n-1 ... and so on.
nC2 + n-1C2 + n-2C2 + ... + 2C2

Tree permutations

Write a program to calculate the different number of tree structures possible,
given n identical values.
For Example:

    For one node, the tree is a trivial one node tree.
    For two nodes, two combinations are possible:
    O               O
     \      and    /
      O           O

    For three nodes :
      O      O      O      O        O
     /      /      / \      \        \
    O      O      O   O      O        O
   /        \                 \      /
  O          O                 O    O

Answer:

/*
For the above diagrams, we can see the recursive property,
i.e, 
For given N nodes:
* One node becomes the root
* Divide the remaining N-1 nodes between left and right subtrees, and this can be
  done as follows:
  Left Subtree              Right Subtree
      0                         N-1
      1                         N-2
      2                         N-3
      ...                       ...
     N-1                         0

  Summing up the above combinations, to get the value of N, 
  The solution can be recursively defined as following:

            { 1 if n == 1  }
  F(n) =    { sigma( F(i) * F(n-i-1 ) where i = 0 to n-1 }

  note that its F(i) * F(n-i-1) , product, not a sum because its a combinatorics problem,
  If event A can be in m ways, and another event B can be done in n ways, then the total
  possible events are (m x n)

  Note that optimization can be achived by caching the results in the recursive call.


*/


#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
// the cache used to "cache the results in a recursive call"
vector cache;
size_t TreeCombinations(size_t n)
{
    if ( (n == 1) || (n == 0) )
        return cache[n];
    // Check if the result was already computed
    if ( cache[n] != 0 )
        return cache[n];
    else
    {
        int i = 0;
        size_t combinations = 0;
        //printf("{ %d \n", n);
        for ( i =0 ; i <= n-1; ++i)
        {
            size_t tmp = TreeCombinations(i) * TreeCombinations(n-i-1);
            //printf(" f(%d) * f(%d) = %d \n", i, n-i-1, tmp );
            combinations += tmp;
        }
        //printf("}\n");
        cache[n] = combinations;
    }

    return cache[n];
}

int main(int argc, char* argv[])
{
    size_t n = atoi(argv[1]);
    // initialize the cache
    cache.reserve(n+1);
    for ( int i = 0; i <= n; ++i )
    {
        cache[i] = 0;
    }
    cache[0] = 1;
    cache[1] = 1;
    // ----
    return printf("Tree combinations for %d nodes = %d \n", n, TreeCombinations(n) );
}

combinations

Print all combinations of M members of a set of N elements in a sequence such that each set can be obtained from the previous set by deleting one member and adding one member.

or Rather print ⁿC_r

Answer:

#include "stdio.h"
#include "iostream"
#include "algorithm"
#include "iterator"
#include "assert.h"
using namespace std;

int main(int argc, char *argv[])
{
    const size_t n = atoi(argv[1]);
    const size_t k = atoi(argv[2]);
    cout << "N = " << n << " k = " << k << endl;
    assert ( (k <= n) && (k > 0));
    size_t *array = new size_t[n];
    size_t up = 0;
    size_t down = 0;
    int i = 0;
    // Initialize the arrray
    for (i = 1; i <= n; ++i) array[i-1] = i;

    for ( up = 0 , down = up+k-1; down < n; ++up , ++down)
    {
        printf(" \n up %d down %d \n", up, down);
        for( i = down; i < n; ++i )
        {
            swap( array[down], array[i] );
            //--- Print the combination ---
            for(int k = up; k<=down; ++k)
                cout << array[k] << " ";
            cout << endl;
            //--- End Print the combination ---
            swap( array[i], array[down] );
        }

    }
    return 0;
}