how can i find all possible combination of a decision tree?
5 views (last 30 days)
Show older comments
hello all ,
for a project that i am doing
a team can score 1 goal or 2 goal per move , if someone told me that the end score between 2 teams was for example was 2:2
i need to find out all possible ways to reach that score
in this case its :
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/152482/image.jpeg)
so in this case the answer is 60
but if someone told me that the end score was 3:2 or 8:8 how can i find out the number of possible ways to reach that score?
Thanks joe
1 Comment
jgg
on 4 Dec 2015
I'm not sure what the answer is here, but it seems like this would be easiest if you augment the scores with a zero score, then add the rule if that last round 0 was scored, then this round zero cannot be scored, and have the teams alternate.
Then, you could just write a program to solve this recursively using a tree transit algorithm with halting criteria that stop if it reaches the desired score or encounters two sequential zero moves.
I'd bet there's a concise analytical answer, though.
Answers (1)
arich82
on 5 Dec 2015
There's a very good chance I've made several errors here, but this might get you started:
We seek the final score of a:b.
We'll first consider the rounds when Team A scores independently from the rounds when Team B scores. (I'm assuming that only one team can score per round, and one team MUST score; the scoring team can earn one or two points [never zero].)
If Team A earned only one point in each of its scoring rounds, it would need a rounds to achieve a points. In general, it needs at most a scoring rounds, and at least ceil(a/2) scoring rounds.
Let n1 be the number of scoring rounds where Team A scores one point, and n2 the number of two-point rounds; clearly a = 1*n1 + 2*n2, with 0 <= n1 <= a, 0 <= n2 <= floor(a/2), and the total nrounds = n1 + n2.
For a given pair of n1 and n2, the number of possible ways for Team A to achieve a points is (n1 + n2)!/(n1!*n2!) (I think; please correct me if I'm wrong...). [To compute this, I thought about how to assign the values 1:nrounds to two groups: one with n1 spots, and one with n2 spots.]
To compute the above, consider the function:
function out = nways(score)
% out(:, 1) = nrounds to achieve score
% out(:, 2) = number of possible ways to achieve score in nrounds
N2 = 0:floor(score/2);
out = NaN(numel(N2), 2);
for k = 1:numel(N2) % for n1 = mod(a, 2):2:a
n2 = N2(k);
n1 = score - 2*n2;
out(k, :) = [n1 + n2, factorial(n1 + n2)/(factorial(n1) * factorial(n2))];
end
end % function nways
I haven't had time to verify the rest, but see if this code dump works. I'll try to check back on Monday.
a = 2;
b = 2;
out_a = nways(a);
out_b = nways(b);
count = 0;
for ka = 1:size(out_a, 1)
nrounds_a = out_a(ka, 1);
nways_a = out_a(ka, 2);
for kb = 1:size(out_b, 1)
nrounds_b = out_b(kb, 1);
nways_b = out_b(kb, 2);
count = count + nways_a*nways_b*factorial(nrounds_a + nrounds_b)/(factorial(nrounds_a) * factorial(nrounds_b));
end
end
0 Comments
See Also
Categories
Find more on Loops and Conditional Statements in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!