how can i find all possible combination of a decision tree?

16 views (last 30 days)
eyal lampel on 4 Dec 2015
Answered: arich82 on 5 Dec 2015
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 :
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
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.

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