Joy precedes competition.

Game && Jaguareins

Generating permutations of a word

with one comment

Here is the code for generating all permutations of a word having all distinct characters, I wrote at Barista few days back.

Input : anyword  Output : All possible permutations of the word, followed by number of permutations.

/* Generating permutations - character word_count
 * of every alphabet being 1 for simplicity.
 * Algorithm design type - Backtracking.
 */
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

#define all(c) c.begin(),c.end()

using namespace std;

vector word;
int word_len, word_count;
ostream_iterator output( cout, "" );

void
generate_permutations(vector &intree_word, int sub_len)
{
    if ( sub_len == word_len-1 ){
        copy( all( intree_word ), output );
        word_count += 1;
        cout << endl;
        return;
    }
    int i;
    char tmp_ch;
    vector temp_word( all( intree_word ) );
    for (i=sub_len; i<word_len; i++){
        tmp_ch = temp_word[i];
        temp_word[i] = temp_word[sub_len];
        temp_word[sub_len] = tmp_ch;
        generate_permutations( temp_word, sub_len+1 );
        temp_word = intree_word;
    }
}

int main()
{
    char ch;

    while ( ( ch = getchar () ) != '\n' )
        word.push_back( ch );
    word_len = word.size();
    cout << endl;
    word_count=0;
    generate_permutations(word, 0);
    cout << "Number of permutations : " << word_count << endl;

    return 0;
}

Happy hacking!

Advertisements

Written by LaFolle

October 6, 2009 at 20:39

Posted in Uncategorized

Tagged with ,

One Response

Subscribe to comments with RSS.

  1. Good work. Nice to see that you are coming up with results rather than just attempts as you previously were. Keep it up.

    Rupak Banerjee

    October 12, 2009 at 04:46


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: