Drawing Blanks

Premature Optimization is a Prerequisite for Success

Permutation or a time zip?

leave a comment »

The title does make sense because it’s an anagram of “premature optimization”. (Found via Xworder , of course).

Permutation generation is another combinatorial algorithm that is NOT used in Xworder. Same story as with powersets (see prev. post). But unlike with powersets, with permutations I didn’t even try to write a fancy algorithm that recurses over enumerators. I prematurely resorted to the good old iterative algorithm shown below (I think it’s due to Knuth).  BTW, here is a really really cool post (in a really really cool blog) about efficient recursion in functional programming http://community.bartdesmet.net/blogs/bart/archive/2009/11/08/jumping-the-trampoline-in-c-stack-friendly-recursion.aspx . Unfortunately, I lack brain power to fully understand it 😦

Anyway, here is the permutation algorithm (you need to start with 1, 2, 3, …, n):

        private bool NextPermutation(int[] values)
        {
            int n = values.Length;

            int i = n - 1;
            while (i > 0 && values[i - 1] >= values[i])
                i--;
            if (i == 0)
                return false;

            int j = n;
            while (values[j - 1] <= values[i - 1])
                j--;

            Swap(values, i - 1, j - 1);
            i++;
            j = n;

            while (i < j)
            {
                Swap(values, i - 1, j - 1);
                i++;
                j--;
            }

            return true;
        }
Advertisements

Written by bbzippo

11/10/2009 at 8:54 am

Posted in programming

Tagged with

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

%d bloggers like this: