Thread Subject: Search path algorithm

I was wondering if, given a goal in terms of final position to reach, it could be possible to calculate all the possible paths constraining the movements to right and down
example:
lets assume the goal is in 9.
1 4 7
2 5 8
3 6 9
then all the possible paths here are
4 7 8 9
4 5 6 9
4 5 8 9
2 3 6 9
2 5 6 9
2 5 8 9
I think a recursive engine could do the trick but could it be posiible to avoid cell storage?

This script calculates the first path in the example...just an attempt to accomplish a bigger picture.

board = reshape(1:9,3,[]);
sz = size(board);
inPos = 1;
cont = 0;
Out = zeros(1,sum(sz)-2);
goOn = true;
finPos = 9;
while goOn
    cont = cont+1;
    % Go to the right
    if inPos/sz(2) < sz(2)-1
        inPos = inPos + sz(1);
        Out(cont) = inPos;
    % Go to the left
    elseif inPos ~= finPos
        inPos = inPos + 1;
        Out(cont) = inPos;
    end
    if cont == length(Out); goOn = false; end
end

Is it the same problem than here?
http://www.mathworks.com/matlabcentral/newsreader/view_thread/253745#657773

Bruno

"Oleg Komarov" <oleg.komarov@hotmail.it> wrote in message <hde28j$hha$1@fred.mathworks.com>...
> I was wondering if, given a goal in terms of final position to reach, it could be possible to calculate all the possible paths constraining the movements to right and down
> example:
> lets assume the goal is in 9.
> 1 4 7
> 2 5 8
> 3 6 9
> then all the possible paths here are
> 4 7 8 9
> 4 5 6 9
> 4 5 8 9
> 2 3 6 9
> 2 5 6 9
> 2 5 8 9
> I think a recursive engine could do the trick but could it be posiible to avoid cell storage?

It looks like a Project Euler problem.

Having said that, if it is, this is the WRONG way
to solve the problem, as it will be far too much
computationally intensive.

John

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hde4p4$99p$1@fred.mathworks.com>...
> Is it the same problem than here?
> http://www.mathworks.com/matlabcentral/newsreader/view_thread/253745#657773
>
> Bruno
Well, I think it is.
I give it a look...

To Jos:
this is what i'd like to verify, if it is worth or not.

A=[1 4 7;
   2 5 8;
   3 6 9;
   10 11 12]

% Engine
[ny nx]=size(A);
dx=allVL1(ny,nx-1);
n = size(dx,1);

p = zeros(n,nx+ny-1);
% This loop can be optimized, map the path to linear index of A
for i=1:n
    x = 1;
    k = 0;
    for j=1:size(dx,2)
        dxij = dx(i,j);
        xj = x+(0:dxij);
        p(i,k+(1:dxij+1)) = sub2ind(size(A),j+zeros(size(xj)),xj);
        x = x+dxij;
        k = k+dxij+1;
    end
end

% Display
p = A(p)

% Bruno

> To Jos:
> this is what i'd like to verify, if it is worth or not.
Typo, John.

To Bruno:
correct me if i'm wrong, your function uses nchoosek, which means the same as going to new york and flying back to london starting from rome.
i was looking for somthing that, under ex-ante constraints, goes right to london. :)

"Oleg Komarov" <oleg.komarov@hotmail.it> wrote in message <hdeh76$q3s$1@fred.mathworks.com>...
> To Bruno:
> correct me if i'm wrong, your function uses nchoosek, which means the same as going to new york and flying back to london starting from rome.
> i was looking for somthing that, under ex-ante constraints, goes right to london. :)

You confuse me or you confuse yourself. You want all paths from A to B so I gave you all paths from A to B by using only steps down/right. If you type your matrix 3x3 example, it gives 6 solutions as you have correctly counted. I have no idea where is London in that grid.

Bruno

"Oleg Komarov" <oleg.komarov@hotmail.it> wrote in message
news:hdeh76$q3s$1@fred.mathworks.com...
> To Bruno:
> correct me if i'm wrong, your function uses nchoosek, which means the same
> as going to new york and flying back to london starting from rome.
> i was looking for somthing that, under ex-ante constraints, goes right to
> london. :)

To get from the upper-left to lower-right corner of an m-by-n grid, you need
to take m-1 steps down and n-1 steps right. It doesn't really matter in
which order you take these steps. So the number of paths is (m+n-2) choose
(m-1) [the total number of steps is (m+n-2), and we choose at which steps we
want to move down] or (m+n-2) choose (n-1) [choosing when we move right].
Thus Bruno's code is correct to use NCHOOSEK to compute the number of
possible paths.

http://mathforum.org/library/drmath/view/66728.html

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ

"Steven Lord" <slord@mathworks.com> wrote in message <hdek22$qbk$1@fred.mathworks.com>...
>
> "Oleg Komarov" <oleg.komarov@hotmail.it> wrote in message
> news:hdeh76$q3s$1@fred.mathworks.com...
> > To Bruno:
> > correct me if i'm wrong, your function uses nchoosek, which means the same
> > as going to new york and flying back to london starting from rome.
> > i was looking for somthing that, under ex-ante constraints, goes right to
> > london. :)
>
> To get from the upper-left to lower-right corner of an m-by-n grid, you need
> to take m-1 steps down and n-1 steps right. It doesn't really matter in
> which order you take these steps. So the number of paths is (m+n-2) choose
> (m-1) [the total number of steps is (m+n-2), and we choose at which steps we
> want to move down] or (m+n-2) choose (n-1) [choosing when we move right].
> Thus Bruno's code is correct to use NCHOOSEK to compute the number of
> possible paths.
>
> http://mathforum.org/library/drmath/view/66728.html
>
> --
> Steve Lord
> slord@mathworks.com
> comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
>
Thanks for the enlightment!
To Bruno: i was confused your function provided me with a stright ticket to london! :)

"Oleg Komarov" <oleg.komarov@hotmail.it> wrote in message <hdepgr$e3d$1@fred.mathworks.com>...
> "Steven Lord" <slord@mathworks.com> wrote in message <hdek22$qbk$1@fred.mathworks.com>...
> >
> > "Oleg Komarov" <oleg.komarov@hotmail.it> wrote in message
> > news:hdeh76$q3s$1@fred.mathworks.com...
> > > To Bruno:
> > > correct me if i'm wrong, your function uses nchoosek, which means the same
> > > as going to new york and flying back to london starting from rome.
> > > i was looking for somthing that, under ex-ante constraints, goes right to
> > > london. :)
> >
> > To get from the upper-left to lower-right corner of an m-by-n grid, you need
> > to take m-1 steps down and n-1 steps right. It doesn't really matter in
> > which order you take these steps. So the number of paths is (m+n-2) choose
> > (m-1) [the total number of steps is (m+n-2), and we choose at which steps we
> > want to move down] or (m+n-2) choose (n-1) [choosing when we move right].
> > Thus Bruno's code is correct to use NCHOOSEK to compute the number of
> > possible paths.
> >
> > http://mathforum.org/library/drmath/view/66728.html
> >
> > --
> > Steve Lord
> > slord@mathworks.com
> > comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
> >
> Thanks for the enlightment!
> To Bruno: i was confused your function provided me with a stright ticket to london! :)

If you want to get the number of possible fly to London (and only that), just type

npath = allVL1(ny,nx-1,[],NaN)

It's correct that there is a relation with NCHOOSEK as Steve pointed out.

Bruno