Balance Pool Seeds In Quadrants of Bracket

[cblaze22]

Need help with this question.

http://stackoverflow.com/questions/17793675/balance-pools-into-a-bracket-algorithm

I need to balance say a pool of 4, with each going into one of the 4 quadrants of a bracket.  Not sure how to do that in say c#?

[Ian Wakeling]

I don't think I have really understood your question.   But when I follow the link and look at your first table:

A1 B1 C1 D1 E1 F1 G1 H1
A2 B2 C2 D2 E2 F2 G2 H2
A3 B3 C3 D3 E3 F3 G3 H3
A4 B4 C4 D4 E4 F4 G4 H4

I can imagine superimposing two 4x4 Latin squares like these:

 E  S  N  W  w  n  s  e 
 W  E  S  N  n  s  e  w
 N  W  E  S  s  e  w  n
 S  N  W  E  e  w  n  s

 these might be useful in assigning pairs of players to N S E W, for example if I pair the E and e from columns (1& 5) repectively, then do the same for  cols (2& 6), cols (3 & 7) and finally (4 & 8) I would reproduce the games you have assigned to east.   If you carry on like this pairing S with s, etc would this give an acceptable solution?  I am most likely wrong as I am only guessing at what you want.

[cblaze22]

Not sure but I am trying to find an algoritm that fits those pools to this type of bracket.  You notice there is a sequence, but I haven't been able to put it into code yet.

EAST            WEST
A1              B1  
E4              F4

G2              H2  
C3              D3

H1              G1  
D4              C4

B2              A2  
F3              E3  

SOUTH           NORTH
D1              C1  
H4              G4

F2              E2  
B3              A3

E1              F1  
A4              B4

C2              D2  
G3              H3  

[cblaze22]

I posted a new question here.

http://stackoverflow.com/questions/17930825/matchup-tournament-algorithm-sequence-needs-to-be-translated-to-code (dead link)

[Ian Wakeling]

This is the Latin square behind your example bracket above.

     E W N S

H A  1 2 3 4
D E  4 3 2 1

B G  2 1 4 3
F C  3 4 1 2

so for example to read off the assignments to North you take:

H3 A3 B4 G4
D2 E2 F1 C1

They are in a different order, but are the same pairings.

[cblaze22]

Super interesting.  Now just to translate this to code.  I am doing this in C#, so if anyone has examples please post.

[Ian Wakeling]

It is easy to make a Latin square of any size if you have a MOD function.

Make an n x n array called S with rows and columns indexed by 0,1,2,...,n-1.

Fill every element in the array as follows:

S[ i, j ] = mod( i + j, n) + 1

then you will have a Latin square on the symbols 1 to n.

This will produce a different square to the 4 x 4 example above, but it should lead to an alternative balanced assignment to NSEW.  It will not have always pair 1 with 4 and 2 with 3, but I don't see that you have made this a requirement.  If you have, what patterns are you looking for if there are more than 4 players per pool?

[cblaze22]

A 1 seed in a pool of 4 should always play a 4 seed in one of the other pools. Makes sense since the 1 seed is the best team after round robin play in a pool, and should play a 4 seed.  This would require pools to have the same pool size, but yes I will need to account for pool sizes that maybe larger or even smaller.  I dont know what that will look like yet.  Is there an algorithm that will do what I want instead of the one you gave below?  I did a 4 x 4 and it doesnt look like the matches translate to mine.

[Ian Wakeling]

As you have found the MOD construction will not keep number 1 and 4 seeds together all the time.

I think you may only want powers of two for the elimination tournament, in which case you can construct suitable squares by repeated inflation of the 2x2 square.

1 2
2 1

To get the 4x4 square, first decide on how you are going to pair up the seeds, so (1 4) and (2 3).  Next produce new versions of the 2x2 square using these pairings:

S1     S2
1 4    2 3
4 1    3 2

Inflate the first 2x2 square so that each element 1 or 2, is replaced by S1 or S2 respectively.

so

S1 S2
S2 S1

which becomes

1 4 2 3
4 1 3 2
2 3 1 4
3 2 4 1

This is equivalent to the 4x4 square in the older message above, the order of the columns would need to be changed to make it identical (i.e. a different assignment to NSEW).

For the next step up to the 8x8 square, decide on the pairings

(1 8) (2 7) (3 6) (4 5) say.


Define S1 to S4

S1     S2
1 8    2 7
8 1    7 2

S3     S4
3 6    4 5
6 3    5 4

Use the 4x4 square above to produce the 8x8 square (only the first 2 rows below are shown, being derived from the first row 1 4 2 3 above).

1 8 4 5 2 7 3 6
8 1 5 4 7 2 6 3

repeat for the 3 remaining rows of the 4x4 square to complete the 8x8 construction.

Note that it is not necessary to implement this as a recursive routine as the square that is doubled in size can be any Latin square, and so the MOD construction could be used to jump straight to the square that is half the size of one required.

Hope that helps.

[cblaze22]

Ok its making more sense.  One question, I know the EWNS would change on the new array you showed on your previous example.  But is there a pattern on how the actual pool is placed to the left side?  You put H A on the first line, then D E, and so forth.  What pattern did you end up doing to achieve this or did you just put those there because of the bracket setup I already had.  If that is the case, a pattern or sequence on how to do this for bigger brackets is needed.

        E W N S
 
H A  1 2 3 4
D E  4 3 2 1
 
B G  2 1 4 3
F C  3 4 1 2

[Ian Wakeling]

I was only duplicating the setup that you had.  Although you did not discuss it, I assumed there was a reason for always wanting a player from pool A to play a player for pool E.  Pool D against pool H, etc.

[cblaze22]

Interesting, I didn't even notice that each seed in one pool played the same pool but a different seed.  In any case is there a sequence or way to set them up the way you did, or was it just manual? I didnt mean to have A play E each time, it just happened that way when I rotated the participants in their positions all the way to H4.

[Ian Wakeling]

Now I think about it, imposing the restriction that all games are of the form 1-4 or 3-2 may lead you no choice but to play pool against pool.  There is nothing special about my placement of A to H, any random allocation of the 8 letters to 4 pairs would do.

[cblaze22]

Are you sure?  If I go down the line of

A B
C D
E F
G H

doesnt setup A vs E like in my bracket?  The way you set it up it did.  Am I missing something?

[Ian Wakeling]

      E W N S  
   
 A B  1 2 3 4  
 C D  4 3 2 1  
   
 E F  2 1 4 3  
 G H  3 4 1 2 

This would give

A1 v C4
B1 v D4
E2 v G3
F2 v H3

all assigned to East etc...  So A would always be with C.