Anagrams

From Rosetta Code
Revision as of 10:55, 15 January 2009 by 71.106.183.17 (talk)
Task
Anagrams
You are encouraged to solve this task according to the task description, using any language you may know.

Two or more words can be composed of the same characters, but in a different order. Using the word list at http://www.puzzlers.org/pub/wordlists/unixdict.txt, find the sets of words that share the same characters that contain the most words in them.

Ada

<ada> with Ada.Text_IO; use Ada.Text_IO;

with Ada.Containers.Indefinite_Ordered_Maps; with Ada.Containers.Indefinite_Ordered_Sets;

procedure Words_Of_Equal_Characters is 

  package Set_Of_Words is new Ada.Containers.Indefinite_Ordered_Sets (String);
  use Ada.Containers, Set_Of_Words;
  package Anagrams is new Ada.Containers.Indefinite_Ordered_Maps (String, Set);
  use Anagrams;

  File   : File_Type;
  Result : Map;
  Max    : Count_Type := 1;

  procedure Put (Position : Anagrams.Cursor) is
     First : Boolean := True;
     List  : Set renames Element (Position);
     procedure Put (Position : Set_Of_Words.Cursor) is
     begin
        if First then
           First := False;
        else
           Put (',');
        end if;
        Put (Element (Position));
     end Put;
  begin
     if List.Length = Max then
        Iterate (List, Put'Access);
        New_Line;
     end if;
  end Put;

begin 

  Open (File, In_File, "unixdict.txt");
  loop
     declare
        Word : constant String     := Get_Line (File);
        Key  : String (Word'Range) := (others => Character'Last);
        List : Set;
        Position : Anagrams.Cursor;
     begin
        for I in Word'Range loop
           for J in Word'Range loop
              if Key (J) > Word (I) then
                 Key (J + 1..I) := Key (J..I - 1);
                 Key (J) := Word (I);
                 exit;
              end if;
           end loop;
        end loop;
        Position := Find (Result, Key);
        if Has_Element (Position) then
           List := Element (Position);
           Insert (List, Word);
           Replace_Element (Result, Position, List);
        else
           Insert (List, Word);
           Include (Result, Key, List);
        end if;
        Max := Count_Type'Max (Max, Length (List));
     end;
  end loop;

exception 

  when End_Error =>
     Iterate (Result, Put'Access);
     Close (File);

end Words_Of_Equal_Characters; </ada> Sample output: 

abel,able,bale,bela,elba
caret,carte,cater,crate,trace
angel,angle,galen,glean,lange
alger,glare,lager,large,regal
elan,lane,lean,lena,neal
evil,levi,live,veil,vile

C++

<cpp>#include <iostream>

  1. include <fstream>
  2. include <string>
  3. include <map>
  4. include <vector>
  5. include <algorithm>
  6. include <iterator>

int main() { 

 std::ifstream in("unixdict.txt");
 std::map<std::string, std::vector<std::string> > anagrams;

 std::string word;
 size_t count = 0;
 while (std::getline(in, word)) {
   std::string key = word;
   std::sort(key.begin(), key.end());
   // note: the [] operator automatically inserts a new value if key does not exist
   anagrams[key].push_back(word);
   count = std::max(count, anagrams[key].size());
 }

 in.close();

 for (std::map<std::string, std::vector<std::string> >::const_iterator it = anagrams.begin();
      it != anagrams.end();
      it++)
   if (it->second.size() >= count) {
     std::copy(it->second.begin(), it->second.end(),
               std::ostream_iterator<std::string>(std::cout, ", "));
     std::cout << std::endl;
   }
 return 0;

}</cpp> Output: 

abel, able, bale, bela, elba, 
caret, carte, cater, crate, trace, 
angel, angle, galen, glean, lange, 
alger, glare, lager, large, regal, 
elan, lane, lean, lena, neal, 
evil, levi, live, veil, vile,

D

D 1, using Phobos (to download the word list you need the Tango Std Lib). <d> import std.stdio, std.stream;

void main() { 

   string[][string] anags;
   foreach (string w; new BufferedFile("unixdict.txt"))
       anags[w.dup.sort] ~= w.dup;
   int lmax;
   foreach (a; anags)
       lmax = lmax < a.length ? a.length : lmax;
   foreach (a; anags)
       if (a.length == lmax)
           writefln(a);

} </d>

Factor

"resource:unixdict.txt" utf8 file-lines
[ [ natural-sort >string ] keep ] { } map>assoc sort-keys
[ [ first ] compare +eq+ = ] monotonic-split
dup 0 [ length max ] reduce '[ length _ = ] filter [ values ] map .

{
    { "abel" "able" "bale" "bela" "elba" }
    { "caret" "carte" "cater" "crate" "trace" }
    { "angel" "angle" "galen" "glean" "lange" }
    { "alger" "glare" "lager" "large" "regal" }
    { "elan" "lane" "lean" "lena" "neal" }
    { "evil" "levi" "live" "veil" "vile" }
}

Haskell

import Data.List

groupon f x y = f x == f y

main = do
  f <- readFile "./../Puzzels/Rosetta/unixdict.txt"
  let  words = lines f
       wix = groupBy (groupon fst) . sort $ zip (map sort words) words
       mxl = maximum $ map length wix
  mapM_ (print . map snd) . filter ((==mxl).length) $ wix

Sample output: 

*Main> main
["abel","able","bale","bela","elba"]
["caret","carte","cater","crate","trace"]
["angel","angle","galen","glean","lange"]
["alger","glare","lager","large","regal"]
["elan","lane","lean","lena","neal"]
["evil","levi","live","veil","vile"]

J

   (#~a:~:{:"1)(]/.~/:~&>)<;.2]1!:1<'unixdict.txt'
+-----+-----+-----+-----+-----+
|abel |able |bale |bela |elba |
+-----+-----+-----+-----+-----+
|alger|glare|lager|large|regal|
+-----+-----+-----+-----+-----+
|angel|angle|galen|glean|lange|
+-----+-----+-----+-----+-----+
|caret|carte|cater|crate|trace|
+-----+-----+-----+-----+-----+
|elan |lane |lean |lena |neal |
+-----+-----+-----+-----+-----+
|evil |levi |live |veil |vile |
+-----+-----+-----+-----+-----+

Java

The key to this algorithm is the sorting of the characters in each word from the dictionary. The line Arrays.sort(chars); sorts all of the letters in the word in ascending order using a built-in quicksort, so all of the words in the first group in the result end up under the key "aegln" in the anagrams map. <java>import java.net.*; import java.io.*; import java.util.*;

public class WordsOfEqChars { 

   public static void main(String[] args) throws IOException {
       URL url = new URL("http://www.puzzlers.org/pub/wordlists/unixdict.txt");
       InputStreamReader isr = new InputStreamReader(url.openStream());
       BufferedReader reader = new BufferedReader(isr);

       Map<String, Collection<String>> anagrams = new HashMap<String, Collection<String>>();
       String word;
       int count = 0;
       while ((word = reader.readLine()) != null) {
           char[] chars = word.toCharArray();
           Arrays.sort(chars);
           String key = new String(chars);
           if (!anagrams.containsKey(key))
               anagrams.put(key, new ArrayList<String>());
           anagrams.get(key).add(word);
           count = Math.max(count, anagrams.get(key).size());
       }

       reader.close();

       for (Collection<String> ana : anagrams.values())
           if (ana.size() >= count)
               System.out.println(ana);
   }

}</java> Output: 

[angel, angle, galen, glean, lange]
[elan, lane, lean, lena, neal]
[alger, glare, lager, large, regal]
[abel, able, bale, bela, elba]
[evil, levi, live, veil, vile]
[caret, carte, cater, crate, trace]

Perl

<perl>use LWP::Simple; use List::Util qw(max);

my @words = split(' ', get('http://www.puzzlers.org/pub/wordlists/unixdict.txt')); my %anagram; foreach my $word (@words) { 

   push @{ $anagram{join(, sort(split(//, $word)))} }, $word;

}

my $count = max(map {scalar @$_} values %anagram); foreach my $ana (values %anagram) { 

   if (@$ana >= $count) {
       print "@$ana\n";
   }

}</perl> Output: 

alger glare lager large regal
abel able bale bela elba
evil levi live veil vile
angel angle galen glean lange
elan lane lean lena neal
caret carte cater crate trace

Python

Python 2.5 shell input (IDLE) <python>>>> import urllib >>> from collections import defaultdict >>> words = urllib.urlopen('http://www.puzzlers.org/pub/wordlists/unixdict.txt').read().split() >>> len(words) 25104 >>> anagram = defaultdict(list) # map sorted chars to anagrams >>> for word in words: anagram[tuple(sorted(word))].append( word )


>>> count = max(len(ana) for ana in anagram.itervalues()) >>> for ana in anagram.itervalues(): if len(ana) >= count: print ana


['angel', 'angle', 'galen', 'glean', 'lange'] ['alger', 'glare', 'lager', 'large', 'regal'] ['caret', 'carte', 'cater', 'crate', 'trace'] ['evil', 'levi', 'live', 'veil', 'vile'] ['elan', 'lane', 'lean', 'lena', 'neal'] ['abel', 'able', 'bale', 'bela', 'elba'] >>> count 5 >>></python>

Ruby

require 'open-uri'

words = open('http://www.puzzlers.org/pub/wordlists/unixdict.txt').read.split anagram = Hash.new {|hash, key| hash[key] = []} for word in words 

 anagram[word.split().sort] << word

end

count = anagram.values.map {|ana| ana.length}.max for ana in anagram.values 

 if ana.length >= count
   p ana
 end

end Output: 

["evil", "levi", "live", "veil", "vile"]
["abel", "able", "bale", "bela", "elba"]
["elan", "lane", "lean", "lena", "neal"]
["alger", "glare", "lager", "large", "regal"]
["angel", "angle", "galen", "glean", "lange"]
["caret", "carte", "cater", "crate", "trace"]
Retrieved from "https://rosettacode.org/wiki/Anagrams?oldid=82710"