Re: Routes with exceptions

Re: Routes with exceptions

Thanks for your comment Plato, but I'm not sure you understand my problem completely.

First of all, A comes before B, as I can only more UP or RIGHT, so I can never move from a higher number to a lower one.

So on my way to Z (10,10), I must NOT go through A, B nor C.

Therefore, A would be (2,3), B (4,9) and C (5,4), and finally Z (10,10).

From (0,0) to Z, I can go through A only, B only, C only, A and B, A and C, B and C, or none of A, B or C.

So, I am looking for a way to subtract routes from routes so it gives me all routes from (0,0) to Z where I do not go through any of A, B or C.

If there was only the point A (2,3), the result would be:

From (0,0) to (10,10) = 184,756

From (0,0) to (2,3) = 10

From (2,3) to (10,10) = 6,435

Total routes to avoid (10 x 6,435) = 64,350

Total good routes (184,756-64,350) = 120,406

Thanks :)

Re: Routes with exceptions

Quote:

Originally Posted by

**KINGOLE** Thanks for your comment Plato, but I'm not sure you understand my problem completely.

I assure you that I understand your problem completely.

You did not understand the reply.

If it impossible for any path to pass through both of those points. So it is simple subtraction.

On the other hand, if it is possible for a path to pass through both of those points. So you must count the paths and subtract.

With three points you have more cases to consider.

Re: Routes with exceptions

Thanks!

But what I can't picture in my head, is how to count the paths I need to subtract:

If I count O -> P -> Q -> Z only, what about the ones that goes through only P and those that goes through only Q?

If we use the previous example (0,0) to (10,10):

Total routes = 184,756

Routes through P (3,2) = 64,350

Routes through Q (6,7) = 60,060

Routes from P to Q = 56

That would mean that 56 of the routes through P also goes through Q, and 56 of the routes through Q also goes through P.

So I guess that means that those 56 routes are counted twice and must be subtracted.

Would it be correct to assume that the number of valid routes would then be: 184,756 - (64,350 + 60,060) + 56 = 60,402?

Thanks. :)

**EDIT: **No! :( that's not correct either.

I just ran a small code that shows the result as 79,946, so I'm a bit lost atm.

Re: Routes with exceptions

Okay, did some tests in Excel, and found the way to avoid 2 points P and Q on the route.

184,756 = A→D

64,350 = A→B→D

60,060 = A→C→D

19,600 = A→B→C→D

79,946 = (A→D) - (A→B→D) - (A→C→D) + (A→B→C→D)

Now I "just" need to completely understand why that is, and test it with 3 points.

**EDIT:** Okay, 3 points threw me off again. Need to do more thinking... Any help will be greatly appreciated! :)

http://king-ole.com/images/p408q.png

Re: Routes with exceptions

I will work this one out for you.

**A would be (2,3), B (4,9) and C (5,4), and finally Z (10,10).**

We want to avoid those three points.

The number of paths through X is denoted by

So

The number of paths through at least one of A, B, or C is:

(note there are no paths thru both B&C). Subtract that from the total to get the number of paths thru none of those points.

Re: Routes with exceptions

Thanks Plato, very much appreciated.

What would that look like if there could be a path through all three (A,B,C) = A(2,3), B(5,5), C(6,7), and Z(10,10)?

If I can grasp that, I should be able to understand n points where n > 3 as well.

Thanks.

Re: Routes with exceptions

Quote:

Originally Posted by

**kingole** what would that look like if there could be a path through all three (a,b,c) = a(2,3), b(5,5), c(6,7), and z(10,10)?

This is known as inclusion/exclusion. It counts the number of paths thru at least one of a, b, or c.

In the last term counts all paths thru all three:

which in this new case is possible.

You should four terms in that product.

Re: Routes with exceptions

I can't get your first example to give me the correct number (77,629).

When you say ||AB|| do you mean ||A|| x ||B|| or (0,0) -> A -> B -> Z?

Thanks.

Re: Routes with exceptions

Quote:

Originally Posted by

**KINGOLE** When you say ||AB|| do you mean ||A|| x ||B|| or (0,0) -> A -> B -> Z?

is (the number from 0 to A) times (the number from A to B) times (the number from B to Z).

Re: Routes with exceptions

Oh, I get your previous example now.

The result I get using http://latex.codecogs.com/png.latex?...-\|AB\|-\|AC\| has to be subtracted from the total amount of routes from 0 to Z. :)

Here's my calculation:

http://king-ole.com/images/p408bad.png

Thank you so much for your help.

I will try the same with your last example, and see if I get it. ;)

**EDIT:** Did the one where all points could be passed in one go, and it came out correctly to 62,502:

http://king-ole.com/images/p408ex2.png

Now I need to test with more points.

My hope is that if I have 6 points (A,B,C,D,E,F) and the possible combinations are (0,A,B,F,Z), (0,B,C,D,F), and (0,A,D,Z) to have the result:

||0Z|| - ||A|| + ||B|| + ||C|| + ||D|| + ||E|| + ||F|| - ||0ABFZ|| - ||0BCDF|| - ||0ADZ||

but I have a feeling it's not going to be that easy... (Thinking)

Thanks again for your help - I truly appreciate it.