Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

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

by LanX (Saint)
on Mar 22, 2018 at 09:39 UTC ( [id://1211498]=note: print w/replies, xml ) Need Help??


in reply to compute paths in Pascal's triangle (aka Tartaglia's one)

All paths have the same number of left right moves which is determined by the end point.

Like 3-1 has 3 left 2 left (*) and 1 right move.

You could easily do a recursion which checks and decrements $l and $r.

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

*) see Re: compute paths in Pascal's triangle (aka Tartaglia's one) (2 updates) for explanation

Replies are listed 'Best First'.
Re^2: compute paths in Pascal's triangle (aka Tartaglia's one)
by LanX (Saint) on Mar 22, 2018 at 10:43 UTC
    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

      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;

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1211498]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others learning in the Monastery: (3)
As of 2024-03-29 04:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found