wood burning stoves*
The moose likes Programming Diversions and the fly likes Lattice Paths Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Lattice Paths" Watch "Lattice Paths" New topic
Author

Lattice Paths

Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986
Imagine Cartesian coordinate grid,with x and y as integer values.Object is moving from (0,0) to (10,6).Object can ONLY move right or above and not in any other way.In how many ways object can move from source to destination?


Namma Suvarna Karnataka
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 556
    
    7

8008
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10916
    
  12

isn't this a simple application of pascal's triangle?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 556
    
    7

that's how i solved it. - or really combination of 16 things taken 6 at a time.
[ June 28, 2006: Message edited by: Steve Fahlbusch ]
Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986
Thats right.16C6 or 16C10 is the answer.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 988
    
    1
Originally posted by Steve Fahlbusch:
8008


I only found 8007 of them. I must have missed one.

Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986
Originally posted by Ryan McGuire:

I only found 8007 of them. I must have missed one.


Are you writing a prorgam or anything else?
ankur rathi
Ranch Hand

Joined: Oct 11, 2004
Posts: 3830
Originally posted by Arjunkumar Shastry:
Thats right.16C6 or 16C10 is the answer.


How did you calculate??? And what is C???

[ October 25, 2006: Message edited by: rathi ji ]
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 988
    
    1
Originally posted by rathi ji:


How did you calculate??? And what is C???


[ October 25, 2006: Message edited by: rathi ji ]




Or xCy is the (x,y) in Pascal's Triangle:



The value of a cell is the sum of the value in the cells directly above and above to the left of it.

In other words:


xCy is the number of ways to select a set of y elements out of a super set of x elements. I there are twelve socks in a drawer, how many different pairs could I possibly pull out? The answer is 12C2.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 988
    
    1
Originally posted by rathi ji:


How did you calculate??? And what is C???


[ October 25, 2006: Message edited by: rathi ji ]


As for how this relates to the original problem...

I'm sure people started out with easier version of the problem:

Starting at the origin and only moving up and/or right, how many paths lead to...
  • (1,0)? That's easy... 1
  • (0,1)? Also easy: 1
  • (anything positive, 0)? Well if I even move up off the x axis, I can never move back down, so the answer is 1.
  • (0, anything positive)? Similar reasoning... 1.
  • (1,1): The second-to-last move to get to (1,1) must have gone through either (1,0) or (0,1). Therefore the number of paths to (1,1) is the sum of the paths leading to (1,0) and the paths leading to (0,1). 1+1=2
  • any (x,y) where x and y are both > 0: the sum of the paths leading to (x,y-1) and the paths leading to (x-1,y).


  • If you plot the first few values on a piece of graph paper...
    ...the numbers start to look really familiar. It doesn't take long to notice that number of ways to get to (x,y) is (x+y)Cx (which is equal to (x+y)Cy).

    Cool?
    [ October 26, 2006: Message edited by: Ryan McGuire ]
    ankur rathi
    Ranch Hand

    Joined: Oct 11, 2004
    Posts: 3830
    Originally posted by Ryan McGuire:



    Cool?



    Super cool. You are genius man.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Lattice Paths
     
    Similar Threads
    two object transparent
    Significant difference between if:loop and loop:if?
    ejb3 primary key generation does not work without automatic schema generation
    Dan Chisholm's Topic Exam
    Wolf, Goat and Cabbage problem solution