wood burning stoves*
The moose likes Programming Diversions and the fly likes Another horse race Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Another horse race" Watch "Another horse race" New topic
Author

Another horse race

Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
In a horse race there are N horses.In how many ways they can finish the race?


MH
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923

Assuming two horses, they can finish:
1-2
2-1
(1,2) dead race
1 (2 DNF)
2 (1 DNF)
(1,2 DNF)

DNF: Did not finish. (Horse lost jockey, for instance).
Instead of DNF disqualification could occur.
But the difference isn't important for betters or price-money.

Do you have a more clean abstract idea of 'finishing' a race.

Of course we should argue, whether 'did not finish' is a way to finish.
Sounds absurd.


http://home.arcor.de/hirnstrom/bewerbung
Francis Siu
Ranch Hand

Joined: Jan 04, 2003
Posts: 867
In how many ways they can finish the race?
If I understand what you ask
Um..........
Assume that there are n horse and without any accident within the racing
the permutation will be nx(n-1)....x1 ==n!

If one accident occurs
the permutation will be 2(n)x2(n-1)....x1== 2(n)!-1

If there are k accident
the permutation will be k(n)xk(n-1)x....x1== k(n)!-(k-1)

It may be wrong
Does it require to write a program to show it out all the permutation and generate it out?
[ October 05, 2004: Message edited by: siu chung man ]

Francis Siu
SCJP, MCDBA
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
No accident.Assume everything goes well.
Suppose there are two horses,1 and 2 then race can be finished as
1 finished the race followed by 2
1 and 2 finish at the same time.
2 finished the race followed by 1
So there are three ways in which 2 horses can finish the race.
Hope this helps.
Stefan Wagner
Ranch Hand

Joined: Jun 02, 2003
Posts: 1923

Excluding dead-race, we get n! results for n horses.

But how many dead-races are possible?
n possibilities
1 0
2 1
3 7
4 ... ?

Hm.
With result of the race, are we interested in every position, or only in the first 3 horses?
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
Yes,dead race means reaching at same time ,right? if we exclude that then n! possibilities.But we want to consider dead race!!.That is interesting.Actually its integer partition problem.
Say there are 4 horses then 4 can be partitioned as
4----Means all arrive at same time
1+1+2(one followed by second and rest arrive at same moment).Now 2 horses can be chosen in 6 ways.and another horse in two ways.So there will be 6*3! ways in which this combination can arrive.
in similar fashion,
1+1+1+1 Each arrives at different time,4!,24 ways
1+3---4*2! ways
2+2---6 ways
In all there are 75 ways
How to generalize for N?I am not sure.
Arjun Shastry
Ranch Hand

Joined: Mar 13, 2003
Posts: 1874
Is there any similarity between this and factorization of a number.?
Say number is 24.Factors are 2,2,2,3.Number of ways in which 24 can be factored are
2*(12),2*2*(6),2*3*(4),2*2*2*3,3*(8),4*6
shankar vembu
Ranch Hand

Joined: May 10, 2001
Posts: 309
Originally posted by Arjun Shastry:
Is there any similarity between this and factorization of a number.?
Say number is 24.Factors are 2,2,2,3.Number of ways in which 24 can be factored are
2*(12),2*2*(6),2*3*(4),2*2*2*3,3*(8),4*6


Let me try.
1. No dead races(one winner) = n!
2. 2 winners = nc2*(n-2)!
We have nc2 ways to choose 2 winners. The rest (n-2) can be arranged in (n-2)!

So on and so forth.

Total = nc1*(n-1)! + nc2*(n-2)! + nc3*(n-3)! + ....+ ncn(n-n)!

Notes: First term = n! is essentially point# 1 stated above.
Last term = 1 = all horses are winners


Is this OK?

SHankar.
[ October 25, 2004: Message edited by: shankar vembu ]
shankar vembu
Ranch Hand

Joined: May 10, 2001
Posts: 309
Originally posted by shankar vembu:


Let me try.
1. No dead races(one winner) = n!
2. 2 winners = nc2*(n-2)!
We have nc2 ways to choose 2 winners. The rest (n-2) can be arranged in (n-2)!

So on and so forth.

Total = nc1*(n-1)! + nc2*(n-2)! + nc3*(n-3)! + ....+ ncn(n-n)!

Notes: First term = n! is essentially point# 1 stated above.
Last term = 1 = all horses are winners


Is this OK?

SHankar.

[ October 25, 2004: Message edited by: shankar vembu ]


I assumed that dead race applies only to position 1.
A more general solution would be:

Let A(n) = total no. of arrangements for n horses(where dead races are possible in every position).
So A(n) = nc1.A(n-1) + nc2.A(n-2) + nc3.A(n-3).........
where (recurse....)
A(n-1) = (n-1)c1.A(n-2) + (n-1)c2.A(n-3) + (n-1)c3.A(n-4)......
A(n-2) = (n-2)c1.A(n-3) + (n-2)c2.A(n-4) + (n-2)c3.A(n-5)......
.
.
.
.
.
I guess I am near to the solution. Any other formulations?
Basically, this would be a "bottom-up" computation.

SHankar
[ October 25, 2004: Message edited by: shankar vembu ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Another horse race
 
Similar Threads
XPath Parent Node Problem
WA #1.....word association
25 horses to win, place, show
reusing threads
WA #2 ..... word association