Perl: the Markov chain saw PerlMonks

### Re: I need help with some recursion

by tobyink (Abbot)
 on Dec 08, 2012 at 11:18 UTC ( #1007888=note: print w/replies, xml ) Need Help??

in reply to I need help with some recursion

To do recursion you really need to do your work in a function. That way, the function can call itself - recurse.

Right now the only function you have is a small helper, uniq and you're not doing the bulk of your work in a function.

Anyway, here's how I'd do it...

```use strict;
use warnings;
use Data::Dumper;

# Read the data from the file...
#
my @lines = map { chomp; [split] } <DATA>;

# Arrays are indexed from 0, but we want to count lines
# from 1, so let's unshift a dummy 0 entry onto the array.
#
unshift @lines, undef;

# This is a more usual way of implementing "uniq". It
# preserves the original input order.
#
sub uniq
{
my %seen;
grep { not \$seen{\$_}++ } @_;
}

# This is the function that does most of the work. It
# calculates what graph theorists would call a "closure"
# over the graph of line references.
#
sub line_closure
{
# We're given an input list, which is a set of
# lines already in the closure.
#
my @input  = @_;

# Extend the list by looping through @input to
# generate the output.
#
my @output = uniq map {
# if the line referred to exists
\$lines[\$_]
# then add the numbers from that
# line
? (\$_, @{\$lines[\$_]})
# otherwise, just keep the existing
# number
: (\$_)
} @input;

# If the two lists match (and because we're only
# ever adding to the list, checking the list
# lengths is sufficient), then we've found the
# closure, so return it.
#
if (@output == @input)
{
return @output;
}

# Otherwise, calculate the closure on the expanded
# list.
#
return line_closure(@output);
}

# Get the closure starting at line 1.
#
my @results = line_closure(1);

print Dumper \@results;

__DATA__
1 2 4
2 3 4
3 7
4 6
5 10 11 12 13
6
7 1
perl -E'sub Monkey::do{say\$_,for@_,do{(\$monkey=[caller(0)]->[3])=~s{::}{ }and\$monkey}}"Monkey say"->Monkey::do'

Replies are listed 'Best First'.
Re^2: I need help with some recursion
by ragnarokPP (Initiate) on Dec 08, 2012 at 11:51 UTC

It is perfect, simple. But if i applied it for all the lines the result will be:

```1,2,4,3,6,7
2,3,4,7,6,1
3,7,1,2,4,6
4,6
5,10,11,12,13
6
7,1,2,4,3,6

but i am looking for something like this:

```1,2,4,3,6,7
5,10,11,12,13

So don't apply it to all the lines. This seems to produce something close to your desired output:

```my %seen;
for (my \$i = 1; \$i < @lines; \$i++)
{
next if \$seen{\$i};
my @results = line_closure(\$i);
print Dumper \@results;
\$seen{\$_}++ for @results;
}
perl -E'sub Monkey::do{say\$_,for@_,do{(\$monkey=[caller(0)]->[3])=~s{::}{ }and\$monkey}}"Monkey say"->Monkey::do'

it seems work perfect. thank you very much.

thank you very much

Create A New User
Node Status?
node history
Node Type: note [id://1007888]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (12)
As of 2017-06-27 14:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (607 votes). Check out past polls.