2
$\begingroup$

I'm trying to calculate the best and worst position for each team in the ranking based on the weekly matches.

Suppose we have 4 teams with these position:

Pos.| Name | Pts.

1 | Team A | 12

2 | Team B | 10

3 | Team C | 8

4 | Team D | 6

And during the week there are 2 matches A vs C and B vs D

If you don't know, in soccer you can win, lose or draw. A win are 3 points, draw 1 points each, lose 0 points.

In this scenario we have 9 possible combinatiosn [3^(number of matches)].

What I want to do is calculate the best and worst position each team can get based on all combination.

Of course is fairly simple to do with 4 teams (2 matches), but in real case scenario we would have about 10 matches (59000 combinations).

I guess the best way to approach the problem is to use recursion but I can't get to a real starting point.

Any help?

Improve this question
$\endgroup$
4
  • $\begingroup$ This seems like a programming question, so off-topic here. $\endgroup$
    – Yuval Filmus
    Sep 6, 2017 at 17:17
  • $\begingroup$ @YuvalFilmus The acceptance of a rather programmy answer notwithstanding, I think it's algorithms. No language is specified and Gregory proposes recursion as a general technique. There's an interesting algorithmic question in whether one can do better than brute force (e.g., there are situations where no possible result could change the ordering). $\endgroup$
    – David Richerby
    Sep 6, 2017 at 17:57
  • $\begingroup$ I wasn't sure if stackoverflow was better than here. My objective was to have an idea on how to write the algorithm for this problem without a specific language in mind, since with pseudo code you can easily rewrite it in any language. Since it was my first time posting in CS I searched and read this answer meta.stackexchange.com/a/129632 which say that this question could be posted in CS or SO. $\endgroup$
    – Gregory Wullimann
    Sep 6, 2017 at 18:05
  • $\begingroup$ Isn't the best position for a team when it wins all games? In this case this team has $6*n$ points. And the worst position when the team loses all games with 0 points. I guess your question shouldn't be that simple, perhaps I misunderstand you, don't I? $\endgroup$
    – fade2black
    Sep 7, 2017 at 22:59

1 Answer 1

Reset to default
1
$\begingroup$

Here's an alternative to recursion:

You have 3 different outcomes. You can assign each outcome to a digit in $[0, 1, 2]$. E.g. 0 means loosing, 1 means draw, 2 means win.

Then you can represent one combination as a series of digits, e.g. $[1, 1, 2, 0, ...]$ (first two matches ended in a draw, the third one was won, ...). And you can interprete this series as the digits of a number in base 3.

So obviously all combinations can be described using a number between $0$ and $3^{\#matches}-1$ and you can very easily iterate over them: 

for combination in 0 .. 3^(#matches)-1:
    results = combination in base 3 (exactly #matches digits)
    process results
Improve this answer
$\endgroup$
6
  • $\begingroup$ This is the same as recursion. $\endgroup$
    – Yuval Filmus
    Sep 6, 2017 at 15:50
  • 1
    $\begingroup$ @YuvalFilmus How? Recursion is a function applied in its own definition. This doesn't apply to my approach at all. I enumerate all possible combinations, iterate over their indices and convert the indices to combinations. Generating the combinations recursively would mean, that in the first recursive call you fixate the outcome of the first game, in the second recursive call the outcome of the second game, ... Of course I generate the combinations in the exact same order as a recursive solution would do it, but the computations are done completely without any recursive calls. $\endgroup$
    – Jakube
    Sep 6, 2017 at 16:41
  • $\begingroup$ This solution make a lot of sense. I'm quite bad with recursions and these was so simple! I had the same reasoning on paper but I was too focused on doing it recursively. Thanks! $\endgroup$
    – Gregory Wullimann
    Sep 6, 2017 at 16:53
  • 1
    $\begingroup$ You answered your own question. Your algorithm is completely equivalent to the recursive solution. It has roughly the same time and space complexity. It's a different implementation of the same idea. The real question is whether you can do any better. $\endgroup$
    – Yuval Filmus
    Sep 6, 2017 at 16:53
  • 1
    $\begingroup$ @YuvalFilmus Yes, they accomplish the exact same thing. But I interpreted the question of OP differently. I don't think he wants a better solution. 3^10 is small enough to try all combinations. He just struggled implementing it. Actually this place might not be the correct place for the question... $\endgroup$
    – Jakube
    Sep 6, 2017 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.