Sunil Jagadish

Archive for the ‘Algorithms’ Category

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).

Advertisements

Written by Sunil

2007.07.18 at 12:47 PM

Posted in Algorithms