005/ch1.pl


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#!/usr/bin/env perl
#
# Write a program which prints out all anagrams for a given word. For more information about Anagram, please check this wikipedia page
# (https://en.wikipedia.org/wiki/Anagram)
################################################################################

use strict;
use warnings;

sub anagrams {
    # Tail-recursive with accumulator; iterate over the word accumulating the
    # anagrams that can be formed with the already-seen characters
    sub iter {
        # @acc contains the already computed anagrams
        my ($word, @acc) = @_;
        if (length($word) == 0) {
            # Finished consuming word -> return accumulator
            return @acc;
        } else {
            # Split the current word: first letter vs the rest
            my ($head, $tail) = $word =~ /^(.)(.*)$/;
            @_ = $tail; # Next word will be the tail of the previous one
            # Compute new anagrams by inserting the current letter in all the
            # positions of the previous anagrams
            foreach my $anagram (@acc) {
                for (my $i = 0; $i <= length($anagram); $i++) {
                    push(@_, $anagram);
                    substr($_[-1], $i, 0) = $head;
                }
            }
            goto &iter;
        }
    }
    iter(shift, (""));
}

for (@ARGV) {
    for (anagrams($_)) {
        print $_, "\n";
    }
}