Generating Integer Partitions in C/C++ (Iterative)

An important thing that any programmer should be able to do is to convert recursive version of an algorithm to iterative version and the reverse. In fact, recently this was highlighted in arstechnica’s article:

http://arstechnica.com/information-technology/2013/04/recursion-or-while-loops-which-is-better/

Below is a particular passage which got my attention:

“…Experience and research suggest that there is a line between people who have the ability to understand variables, pointers, and recursion, and those who don’t. Almost everything else in programming, including frameworks, APIs, programming languages and their edge cases, can be acquired through studying and experience, but if you are unable to develop an intuition for these three core concepts, you are unfit to be a programmer. Translating a simple iterative loop into a recursive version is about the quickest possible way of filtering out the non-programmers—even a rather inexperienced programmer can usually do it in 15 minutes, and it’s a very language-agnostic problem, so the candidate can pick a language of their choice instead of stumbling over idiosyncrasies…”

I like this idea for several reasons and decided to test my own ability to convert a recursive version of an algorithm to iterative one. As a guinea pig, I chose integer partition in C, posted a few weeks ago in recursive form. So below is my iterative version. This was not a trivial conversion – the routine was not tail-recursive, and I had to save a few variables on emulated stack to make it work. Importantly, I’ve done it in less than 15 minutes – just in time appropriate for real programmer as per above article (although directionally the conversion was reversed). I wonder what kind of a test is out there to stratify data analysts? Is there any particular concept like recursion and pointers which a ‘true’ data analyst must understand? I guess functional dependencies, bijections (i.e. one-to-one correspondences) etc. What are your thoughts? (Please nothing SQL specific.)

Let me know if you find any problems with this iterative version, maximal stack height is assumed to be 1000 records but this by no means needs to be the case.
/*
********************************************************************
Author:    Monsi Terdex
Date:    05/01/13
Description:
Integer partition in C (iterative)
********************************************************************
*/


#include <stdio.h>
#include <stdlib.h>


/*
====================
Emulated stack record
====================
*/


typedef struct {
int first;
     int n;
     int level;
} Call;

/*
====================
Routine for printing the splinters of integer
====================
*/


void print(int n, int * a) {
     int i ;
     for (i = 0; i <= n; i++) {
          printf("%d", a[i]);
     }
     printf("\n");
}
/*
====================
Main algorithm for iterative enteger partition
Parameters:


n - the integer to be split
a - array for holding the splinters
Returns: none
====================
*/


void integerPartition(int n, int * a){
     int first;
     int i;
     int top = 0;
     int level = 0;
     // maximal stack height is up to you
     Call * stack = (Call * ) malloc (sizeof(Call) * 1000);
     stack[0].first = -1;
     stack[0].n = n;
     stack[0].level = level;
     while (top >= 0){
          first =      stack[top].first;
          n =           stack[top].n;
          level =      stack[top].level;
          if (n >= 1) {
               if (first == - 1) {
                    a[level] = n;
                    print(level, a);
                    first = (level == 0) ? 1 : a[level-1];
                    i = first;
               } else {
                    i = first;
                    i++;
               }
               if (i <= n / 2) {
                    a[level] = i;
                    stack[top].first = i;
                    top++;
                    stack[top].first = -1;
                    stack[top].n = n - i;
                    stack[top].level = level + 1;
          } else {
               top--;
          }
     } else {
     top --;
     }
}
}
/*
====================
Entry-point
====================
*/
int main(){
     // the integer to be partitioned, in this case 5
     int n = 5;
     // the array for holding the splinters
     int * a = (int * ) malloc(sizeof(int) * n);
     integerPartition (n, a);
     return(0);
}

Advertisements

~ by Monsi.Terdex on May 3, 2013.

One Response to “Generating Integer Partitions in C/C++ (Iterative)”

  1. I was suggested this web site by my cousin. I’m not sure whether this post is written by him as no one else know such detailed about my problem. You’re wonderful!
    Thanks!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Normal Boy

Nothing out of the ordinary

Data Engineering Blog

Compare different philosophies, approaches and tools for Analytics.

%d bloggers like this: