[Israel.pm] sliding window on streaming lines

[Shlomi Fish]

On Sunday 06 June 2004 10:02, Shlomo Yona wrote:
> What I'm looking for, is an elegant way of doing something
> like this:
>
> 	my @all_possible_paths = get_all_possible_paths($lattice);
> 	foreach my $path (@all_possible_paths) {
> 		# do something with $path;
> 	}
>
> Where I expect @all_possible_paths to look like this (I
> don't care about the order of paths but I do care about the
> order of strings within each and every path):
>
> @all_possible_paths = (
> 	['foo', 'moo', 'bar'],
> 	['foo', 'moo', 'baz'],
> 	['foo', 'miau', 'bar'],
> 	['foo', 'miau', 'baz'],
> 	['foo', 'blah', 'bar'],
> 	['foo', 'blah', 'baz']
> );
>

Here's a procedurally-recursive (tree-recursive) implementation of this 
cross-product function in Perl. I haven't thoroughly tested it except for 
this particular example, but it should work:

<<<
#!/usr/bin/perl

use warnings;
use strict;

# I'm using arrays instead of hashes because they are ordered and
# it's easier. If you want to store them as hashes, then convert them
# to arrays before calling the routine.
my $lattice = 
[
    [ qw(foo)],
    [ qw(moo miau blah)],
    [ qw(bar baz) ],
];

my @all_possible_paths = get_all_possible_paths($lattice);
foreach my $path (@all_possible_paths) {
        # do something with $path;
        print join(" <==> ", @$path), "\n";
}

sub get_all_possible_paths
{
    my $lattice = shift;

    my $partial_cross_product;

    my @ret;

    $partial_cross_product = sub {
        my $i = shift;
        if ($i == @$lattice)
        {
            return [[]];
        }
        return 
            [ map { 
                my $this_item = $_; 
                map { [ $this_item, @$_ ] } 
                  @{$partial_cross_product->($i+1)}
            } (@{$lattice->[$i]})
            ];
    };

    return @{$partial_cross_product->(0)};
}
>>>

Note that the perl interpreter and the perl debugger may give you trouble if 
the recursion depth is very large. For a discussion of it see:

http://vipe.technion.ac.il/~shlomif/lecture/LM-Solve/slides/exotic-bugs/recursion_limit.html

Give me some time and I'll also be able to produce a 
non-procedurally-recursive version with an iterator. But doing it with 
recursion is easier and more intuitive.

Regards,

	Shlomi Fish

-- 

---------------------------------------------------------------------
Shlomi Fish      shlomif at iglu.org.il
Homepage:        http://shlomif.il.eu.org/

Quidquid latine dictum sit, altum viditur.
        [Whatever is said in Latin sounds profound.]