There's more than one way to do things PerlMonks

### Re^2: compute paths in Pascal's triangle (aka Tartaglia's one)

by LanX (Sage)
 on Mar 22, 2018 at 10:43 UTC ( #1211500=note: print w/replies, xml ) Need Help??

an hour later oO

I don't like that there are still wrong moves possible*, probably because I din't follow my own concept...

```use strict;
use warnings;
use Data::Dump qw/pp dd/;

my \$goal = [3,1];
my (\$nl,\$nr) = @\$goal;

my @results;

pathfinder( [0,0] );                      # start

pp \@\$_ for @results;

sub pathfinder {
my ( \$last )=@_;

my (\$l,\$r)   = @\$last ;

if ( \$nl == \$l ) {
if (\$nr == \$r){
push @results,[ reverse @_];
}
else {
#warn "wrong",pp \@_;
return
}

}

# left
pathfinder( [\$l+1,\$r  ], @_ ) if \$l != \$nl;

# right
pathfinder( [\$l+1,\$r+1], @_ ) if \$nr != \$r;
}

```[[0, 0], [1, 0], [2, 0], [3, 1]]
[[0, 0], [1, 0], [2, 1], [3, 1]]
[[0, 0], [1, 1], [2, 1], [3, 1]]

Cheers Rolf
(addicted to the Perl Programming Language and ☆☆☆☆ :)
Wikisyntax for the Monastery

*) i.e. the else branch with the warning should never be reached.

##### update

solution here

Replies are listed 'Best First'.
Re^3: compute paths in Pascal's triangle (aka Tartaglia's one)
by hdb (Monsignor) on Mar 22, 2018 at 11:48 UTC

Well, for any given target node you build a string of the correct number of left and right moves (or zeroes and ones) and then any permutation is one of the admissible solutions (and all of them).

UPDATE: Just as illustration, using a module, and having to filter out duplicates in the permutations, it could work like this:

```use strict;
use warnings;
use Algorithm::Permute;

my \$node = '5-2';
my (\$all, \$right) = split /-/, \$node;
my @path = ((0) x (\$all-\$right),(1) x \$right);
my %pathes;
Algorithm::Permute::permute {
my \$key = join '', @path;
if( not exists \$pathes{\$key} ) {
\$pathes{\$key} = 1;
my (\$l, \$r) = (0,0);
my \$path = "(\$l-\$r) ".join( " ", map{ "(".(++\$l)."-".(\$r+=\$_).
+")" } @path);
print "\$path\n";
}
} @path;

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1211500]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
As of 2022-06-28 08:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?