Not Yet Answered # Assigning Fields to Matches

pyTony 888 Gribouillis 1,313

0

8x8 array filled with fields assigned. Could be done with standard search. Assignement is really 3 fields as last is fixed by the third choice. So you have depth three search tree (choosing 2 of 8 teams, 2 of 6 teams and 2 of 4 teams) for each play.

0

I suggest a recursive search where allocated matches are represented by a list of lists

```
F = [
[(0, 1), (2, 4), (3, 6)],
[(2, 3), (0, 7)],
[(4, 5), (1, 6)],
[(6, 7), (3, 5)]
]
```

There are 4 rows in this list, each representing a field. Here, F means that in round 0, teams 0 and 1 played in field 0, teams 2 and 3 played in field 1, teams 4, 5 in f. 2, t. 6 and 7 in f. 3.

In round 1, t 2 and 4 played in f. 0, etc.

We suppose by induction that we have a function `solve(F)`

which returns a solution of the allocation problem (an array where all 4 rows have length 7, which means that the 7 rounds have been allocated) which rows start with the same elements as the argument array F. The function solve(F) returns None if there is no such solution.

Now here is the pseudo-code for solve() if we look for solutions where each team plays at most twice in each field

```
def solve(F):
n = len(F[0])
if n == len(F[-1]): # all rows have the same length
if n == 7: # we have a solution
return F
else:
x = 0
y = n
else:
x = index of first row with length (n - 1)
y = n - 1
# we try to add a new element in position F[x][y] and call solve() recursively
teams = set(range(8))
remove from teams all teams already in column F[.][y]
remove from teams all teams which appear in position F[x][y-1] (if y > 0)
remove from teams all teams which appear twice in row F[x]
teams = sorted(teams)
pairs = union of set(row) for row in F
F[x].append(None)
for i, a in enumerate(teams):
for b in teams[i+1:]:
if (a, b) in pairs:
continue
F[x][y] = (a, b)
rv = solve(F)
if rv is not None:
return rv
del F[x][-1]
return None
```

This algorithm can be improved by passing more parameters to solve(). For example the set 'pairs'... or make solve a method of a State class.

*Edited 3 Years Ago by Gribouillis*

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

the function that I created to find the ...

Hi. so this is actually a continuation from another question of mineHere but i was advised to start a new thread as the original question was already answered.

This is the result of previous question answered :

code for the listbox - datagridview interaction

At the top of the code ...

Hi. I have a form with list box : lst_product, datagridview : grd_order and button: btn_addline. lst_product has a list of product ids selected from database (MS Acess 2013) , grd_order is by default empty except for 2 headers and btn_addline adds rows to grd_order.

btn_addline :

`Private Sub btn_addline_Click(ByVal ...`