[Israel.pm] sliding window on streaming lines

[Shlomo Yona]

On Sun, 6 Jun 2004, Gaal Yahas wrote:

> The idea I had followed basically gives each combination a number,
> whose every digit is in a different base. :-P
> 
> Modulo small details -- perhaps it needs to be zero-based instead of
> one-based as in my previous mail -- I think it's pretty efficient;
> and since we visit each "number" and hence each possible combination,
> it is correct. Is what you mentioned similar to that? I'm not an expert
> in algorithms and yet I get a feeling that there's no need for fancy
> stuff here.

I don't think I understnd you.

Here's an example:

	my $lattice = [
		{
			foo => 1
		},
		{	
			moo => 1,
			miau => 0,
			blah => 0
		},
		{
			bar => 0,
			baz => 1
		}
	];

This lattice represents sevaral possible paths of strings.
Please consider the following regular expression as another
representation of all possible paths:

	/foo(?:moo|miau|blah)(?:bar|baz)/

Thing, is -- I don't want to recognize such "paths of
strings", but instead, I want to generate them (and do
something with each such possible path).

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']
);


(Actually, I'm also interested to know whether the path
contains 1 througout or not, but that's trivial to add
later...)


So -- again -- my problem lies in an elegant way of
producing @all_possible_paths.

Any suggestions?

Thanks.


-- 
Shlomo Yona
shlomo at cs.haifa.ac.il
http://cs.haifa.ac.il/~shlomo/