Sunil Jagadish

Anagrams

with 3 comments

What is an anagram?

Problem: Given a file containing words, re-arrange it such a way that all anagrams appear consecutively.

Example:
Given,
dcba
pqrs
zyx
cbad
xyz
sqrp
abcd

The result should be:
abcd
cbad
dcba
pqrs
sqrp
xyz
zyx

Here is a simple Perl + unix command line which does the job:

#!/usr/local/bin/perl -w

use strict;

open(INP,$ARGV[0]);

while(<INP>) {
   chomp;
   my $sig = join ”, sort split(”,$_);
   print “$sig\t$_\n”;
}

Command line: ./anagram.pl ip.txt | sort | awk -F’\t’ ‘{print $2;}’

Technique: Every word is associated with a signature. Here, a signature is nothing but the word with all the characters in it appearing in sorted order.

Here is how it looks:

abcd    abcd
abcd    cbad
abcd    dcba
pqrs    pqrs
pqrs    sqrp
xyz     xyz
xyz     zyx

Then, awk -F’\t’ ‘{print $2;}’ simply prints the original words (column 2).

About these ads

Written by NorCal Bike Racing

2007.07.18 at 12:47 PM

Posted in Algorithms

3 Responses

Subscribe to comments with RSS.

  1. The similiar question was asked in my interview at GE i believe.. !

    Ranganath.S

    2007.07.26 at 12:47 PM

  2. Cool! What was your solution?

    suniljagadish

    2007.07.26 at 02:33 PM

  3. The solution was same but i didnt mention about the linux command but the logic was same to sign the anagrams and compare. had to write an alogorithm for it.! Infact i had read this on in one of the websites before the interview…

    Ranganath.s

    2007.07.27 at 02:26 PM


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

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: