smgfc has asked for the wisdom of the Perl Monks concerning the following question:

Ok, I am working on a spell checker, and I end up with an array of an array of the possible values of each character (if that character was incorrect), and then I need to print every possible word those chracters can create. So, if i have:
heylo

[download]
as my word, 
hello
heplo
heilo

[download]
as my dictionary (not all real word in this example), my array would be:
@characters = [
    [ "h" ],
    [ "e" ],
    [ "l", "p", "i" ],
    [ "l" ],
    [ "o" ],
]

[download]
how do I print (for example):
The possible words are:
    hello
    heplo
    heilo

[download]
??

Replies are listed 'Best First'.
Quantum::Superpositions to the rescue (was: creating word from array of array)
by Corion (Patriarch) on Feb 16, 2002 at 22:59 UTC

    I have to admit it - Damian Conway changed the way I now look at cartesian products. I haven't exactly understood yet why a join "", @states does not work instead of the foreach, but this is how I'd now attack that problem - manually implementing recursion is so 20th century !

    #!/usr/bin/perl -w
use strict;
use Quantum::Superpositions;

my @characters = (
    [ "h" ],
    [ "e" ],
    [ "l", "p", "i" ],
    [ "l" ],
    [ "o" ],
);

# build up our Quantum Mechanics Automaton
my @states = map { any(@$_) } @characters;

# And print out all possibilities
my $string = "";
$string .= $_ foreach @states;
print join(",",eigenstates($string));

    [download]
    perl -MHTTP::Daemon -MHTTP::Response -MLWP::Simple -e ' ;    # The  
$d = new HTTP::Daemon and fork and getprint $d->url and exit;#spider
($c = $d->accept())->get_request(); $c->send_response( new   #in the
HTTP::Response(200,$_,$_,qq(Just another Perl hacker\n))); ' #  web

    [download]
[reply]
[d/l]
[select]
Re: creating word from array of array
by dvergin (Monsignor) on Feb 16, 2002 at 22:33 UTC
    Let's generalize a little and allow more than one set of variant characters. 
    #!/usr/bin/perl -w
use strict;

# Set up
my @charsets = (
                [ "b", "h" ],
                [ "e" ],
                [ "l", "p", "i" ],
                [ "l" ],
                [ "o" ],
               );

# Do it
my @words = ("");
for my $char_ref (@charsets) {
   my @temp_words;
   for my $word_part (@words) {
      for my $char (@$char_ref) {
         push @temp_words, $word_part . $char;
      }
   }
   @words = @temp_words;
}

# Show it
print "$_\n" for @words;

    [download]
    This prints:
      bello
      beplo
      beilo
      hello
      heplo
      heilo

    ------------------------------------------------------------
    "Perl is a mess and that's good because the
    problem space is also a mess.    " - Larry Wall

[reply]
[d/l]
      hey, this is exactly what i was looking for, i should have made it clear there could be more then one "set of variant characters" (right now i am allowing up to three). Thanks again!
[reply]
Re: creating word from array of array
by blakem (Monsignor) on Feb 17, 2002 at 12:34 UTC
    Warning, sneaky glob trick ahead....
    (should work with 5.6 on all platforms, and 5.005 on unix) 
    #!/usr/bin/perl -wT
use strict;

my @characters = (
                  [ "h" ],
                  [ "e" ],
                  [ "l", "p", "i" ],
                  [ "l" ],
                  [ "o" ],
);

my @words = glob('{'.join("}{",map{join',',@$_}@characters).'}');

print "The possible words are:\n";
print "    $_\n" for @words;

__END__

The possible words are:
    hello
    heplo
    heilo

    [download]

    -Blake

[reply]
[d/l]
Re: creating word from array of array
by Anonymous Monk on Feb 16, 2002 at 22:31 UTC 
    @characters = (
      [ "h" ],
      [ "e" ],
      [ "l", "p", "i" ],
      [ "l" ],
      [ "o" ],
);
sub spell{
    my $prefix = shift;
    my @c = @{+shift};
    unless( @c ){
        return print "$prefix\n";
    }
    foreach( @c ){
         spell("$prefix$_",@_);
    }
}
spell("",@characters);

    [download]
[reply]
[d/l]
      This code fails at "my @c = @{+shift};" with the message, "Can't use an undefined value as an ARRAY reference..."

      Fixing that leads to an endless loop with a warning about an uninitialized value.

      Update: /me puzzles over screamingeagle's results with the same OS and Perl version and wonders why copy-and-paste ain't what it used to be...

[reply]
        fyi...the code ran just fine for me (Windows 98 ,ActiveState Perl 5.6.0)
        (++ for your post too) :-)
[reply]

Back to Seekers of Perl Wisdom