[Israel.pm] sliding window on streaming lines

Shlomo Yona shlomo at cs.haifa.ac.il
Sun Jun 6 00:02:53 PDT 2004

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:


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

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

Any suggestions?


Shlomo Yona
shlomo at cs.haifa.ac.il

More information about the Perl mailing list