I am trying to write some code to solve this math problem: there is 8 teams and all of them will play football game each other (so total of 7+6+...+1 = 28 matches) and they have just two chance of result: win or lose. There are how many combination of at least 1 win and 1 lose for each of the teams. If you couldn't get the question please say and let me try to explain again. The problem is my code prints infinitely increasing numbers(it is an infinite loop, i wrote the print statement in function to understand what the problem is) Here is my code, what is the problem you think? Thank you.
num = 8
team = [0,0,0,0,0,0,0,0]
order = []
how_many_stats = 0
temp = 0
for i in range(num):
for t in range(i+1 , num):
order.append([i,t])
total_matches = len(order) - 1
curr_matches = - 1
def do_match():
global num
global team
global order
global how_many_stats
global temp
global total_matches
global curr_matches
print(how_many_stats)
curr_matches += 1
team[order[curr_matches][0]] += 1 # first wins
if not curr_matches == total_matches:
do_match()
else:
for i in range(num):
if team[i] > 0 and team[i] < 7: #7/8?
temp += 1
if temp == num:
how_many_stats += 1
temp = 0
team[order[curr_matches][0]] -= 1 # take back the action
team[order[curr_matches][1]] += 1 # second wins
if not curr_matches == total_matches:
do_match()
else:
for i in range(num):
if team[i] > 0 and team[i] < 7: #7/8?
temp += 1
if temp == num:
how_many_stats += 1
temp = 0
team[order[curr_matches][1]] -= 1
curr_matches -= 1
return
do_match()
print(how_many_stats)
Explainment: I declared a roadway for the games and took them into an array (1st team vs 2nd team, 1st team vs 3rd team etc.) Then i took them into action in order of that array. Likely builded a tree about wins and loses for each game and a control structure at the end of each branch if this road meets our conditions or not. If meets increase how_many_stats's value for 1 and try the other road by going one step back and so on, if doesn't meet, again look up for the other roads by going 1 step back. If already looked both two nodes below, step back again and so on.
After adding some debug logic in line 21:
print("called do_match with num: %d, team: %s, order: %s, how_many_stats: %d, temp: %d, total_matchs: %d, curr_matches: %d" % (
num, str(team), str(order), how_many_stats, temp, total_matches, curr_matches
))
and letting it run for a bit:
called do_match with num: 8, team: [7, 4, 4, 1, 4, 1, 2, 4], order: [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 4], [3, 5], [3, 6], [3, 7], [4, 5], [4, 6], [4, 7], [5, 6], [5, 7], [6, 7]], how_many_stats: 0, temp: 0, total_matchs: 27, curr_matches: 26
called do_match with num: 8, team: [7, 4, 4, 1, 4, 0, 3, 3], order: [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 4], [3, 5], [3, 6], [3, 7], [4, 5], [4, 6], [4, 7], [5, 6], [5, 7], [6, 7]], how_many_stats: 0, temp: 0, total_matchs: 27, curr_matches: 25
...
called do_match with num: 8, team: [7, 4, 4, 1, 3, 1, 3, 4], order: [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 4], [3, 5], [3, 6], [3, 7], [4, 5], [4, 6], [4, 7], [5, 6], [5, 7], [6, 7]], how_many_stats: 0, temp: 0, total_matchs: 27, curr_matches: 26
called do_match with num: 8, team: [7, 4, 4, 1, 3, 0, 4, 3], order: [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [3, 4], [3, 5], [3, 6], [3, 7], [4, 5], [4, 6], [4, 7], [5, 6], [5, 7], [6, 7]], how_many_stats: 0, temp: 0, total_matchs: 27, curr_matches: 25
I came to the conclusion, that your code does terminate and that your problem is that there are just too many possibilities in your match-tree.
For examples, by reducing the number of teams to 4 and running again it indeed terminates:
called do_match with num: 4, team: [0, 0, 0, 0], order: [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]], how_many_stats: 0, temp: 0, total_matchs: 5, curr_matches: -1
....
called do_match with num: 4, team: [0, 1, 2, 2], order: [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]], how_many_stats: 32, temp: 0, total_matchs: 5, curr_matches: 4
32
So you need to figure out a better algorithm that is able to calculate the number of matches without brute-forcing the match-tree and counting the outcomes that match your requirement of
at least 1 win and 1 lose
For example, you could count the number of possibilities where each team has exactly one win or exactly one loose and subtract that from the total amount of possible outcomes (just make sure to not count them twice as both parts of this or can happen independently)
target=total_number-exactly_one_win-exactly_one_loss+exactly_one_win_and_one_loss