Mike,
Thanks for your effort. Let me elaborate my question. Actually I am
trying to find an optimal route for a Dial-A-Ride problem. Once we
have list of requests that have information like pick up(P) and drop
off(D) time, I am trying to enumurate all the possible route that can
be formed then I am eliminating the invalid routes and reach to valid
route using heuristic approach. I will highly appreciated if anyone
has better approach for such problem.
Thanks
On Jul 18, 4:15 pm, Mike <[EMAIL PROTECTED]> wrote:
> Hi Rupesh,
>
> Despite the fact that the answer may not help you, my colleagues and I
> worked on this problem today. The closed-form solution for two lists
> of size n is as follows:
>
> The number of possible permutations, following your original
> instructions, are:
>
> P(n) = (2*n)! / (n!)^2 - (2*n)! / [(n-2)!*(n+2)!] = (2*n)nCr(n) -
> (2*n)nCr(n-2)
>
> In practice, this number gets very large very quickly. For example,
> the result for n={1,2,...14} is
> P(n) = {1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,
> 742900, 2674440}
>
> The reasons for this are complicated, but contact me if you're
> interested and I'd be glad to elaborate.
>
> Mike
>
> On Jul 17, 11:04 pm, "Rupesh Bhochhi" <[EMAIL PROTECTED]> wrote:
>
>
>
> > Thank you Karthik for your effort. I figure out lately that My
> > question is not that much logical. Actually there will be only one
> > possible combination that we can easily get as we have already got the
> > sorted lists.
>
> > On 7/17/07, Karthik Singaram L <[EMAIL PROTECTED]> wrote:
>
> > > Hi,
> > > Although, I cannot give you a complete solution right now..I will give
> > > you
> > > the following relations (I am not sure If they are correct.....discussions
> > > welcome)
>
> > > T(0, x) = 1
> > > T(x, 0) = 1
> > > T(1, x) = (x+1)
> > > T(x, 1) = (x+1)
> > > T(n, m) = Sum[i=0..n] { T(n-i, m-2) * (i+1) }
>
> > > If you are looking for a program, then you can code this up...If you are
> > > looking for a closed form solution, this needs to be tidied up.
>
> > --
> > Rupesh Bhochhibhoya, [EMAIL PROTECTED]
> > Oklahoma State University
> > Stillwater, OK 74075- Hide quoted text -
>
> - Show quoted text -
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
