Drawing Blanks

Premature Optimization is a Prerequisite for Success

Generating Combinations

with 3 comments

This little function will conclude The Road to Full Anagrams https://bbzippo.wordpress.com/2009/11/27/inside-xworder-the-road-to-full-anagrams/

        int[] GetNextCombination(int n, int[] state)
        {
            int r = state.Length;
            int i = r - 1;
            while (i >= 0 && state[i] == n - r + i)
                i--;

            if (i < 0)
                return null;

            state[i]++;
            for (int j = i + 1; j < r; j++)
                state[j] = state[i] + j - i;            

            return state;
        }

 

The initial state should be 0, 1, 2, …, k.

Now you can glue all pieces together and write your own anagram generator.

Xworder’s Full Anagram mode uses some more tricks to make the search faster and to increase chances of finding good anagrams. For instance, it does not consider partitions that have too many too short words or too many too long words. Also, for certain inputs, it switches to a completely different algorithm that doesn’t use integer partition enumeration at all. That algorithm is much faster, but it is not exhaustive and may result in duplicates. But you may never notice that, since Xworder’s web UI never returns more than 500 anagrams. 

Needless to say, “comfort is” is an anagram of Microsoft. Their free development tools and technologies are the best. But if you don’t like Microsoft, Xworder still may help you express yourself 🙂

OTHER POSTS IN THE “ROAD TO FULL ANAGRAMS” SERIES:

https://bbzippo.wordpress.com/2009/11/27/inside-xworder-the-road-to-full-anagrams/

https://bbzippo.wordpress.com/2009/12/06/inside-xworder-the-road-to-full-anagrams-2/

https://bbzippo.wordpress.com/2009/12/18/integer-partitions/

https://bbzippo.wordpress.com/2010/01/06/generating-combinations/

Advertisements

Written by bbzippo

01/06/2010 at 6:21 am

Posted in programming

3 Responses

Subscribe to comments with RSS.


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: