Round Robin Tournament Scheduling

Schedules - You must register to Post and Download => Requests => Topic started by: cblaze22 on July 26, 2013, 04:13:51 PM

Title: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on July 26, 2013, 04:13:51 PM
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#?
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: Ian Wakeling on July 27, 2013, 08:57:08 AM
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 (http://en.wikipedia.org/wiki/Latin_square) 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.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on July 29, 2013, 01:25:10 PM
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  
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on July 29, 2013, 01:53:11 PM
I posted a new question here.

http://stackoverflow.com/questions/17930825/matchup-tournament-algorithm-sequence-needs-to-be-translated-to-code (dead link)
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: Ian Wakeling on July 30, 2013, 01:37:21 AM
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.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on August 08, 2013, 06:25:25 PM
Super interesting.  Now just to translate this to code.  I am doing this in C#, so if anyone has examples please post.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: Ian Wakeling on August 09, 2013, 01:06:36 AM
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?
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on August 13, 2013, 02:57:32 AM
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.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: Ian Wakeling on August 13, 2013, 06:30:11 AM
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.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on August 13, 2013, 03:47:34 PM
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
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: Ian Wakeling on August 14, 2013, 03:53:38 AM
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.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on August 14, 2013, 11:43:13 AM
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.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: Ian Wakeling on August 15, 2013, 08:36:10 AM
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.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on August 15, 2013, 12:45:29 PM
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?
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: Ian Wakeling on August 16, 2013, 04:36:42 AM
      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.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on August 16, 2013, 12:25:34 PM
So no sequence to get A matched with E unless I specifically place them together?  I also wouldnt want A1 and B1 in the same quadrant.  They should be seperate.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on August 18, 2013, 05:53:10 PM
I think I figured it out.  I can generate a sequence with an algorithm to get

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

Which turns out to be

18  AH  1 2 3 4
45  DE  4 3 2 1

27  BG  2 1 4 3
36  CF  3 4 1 2  

If I take the diagnal as the matchup, or reverse the bottom rows, then I get the correct matchups.  Just need to make this dynamic and make sure it works for other values.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on August 19, 2013, 02:41:19 PM
Would this setup work for a pool that has a different number of participants? So H has 5 participants instead of 4, would the latin square setup still work?
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on August 19, 2013, 06:17:42 PM
I think I got the extra seed in a pool.  I am trying to generate a 8x8 using code.

What is the best way to generate

18452736
81547263
45183627
54816372

and make it dynamic for other latin square sizes.  I am using C# to do this.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on August 19, 2013, 06:56:49 PM
I came up with this and generates my results.  The maxpositions is the matchups, so 18452736.  I just need it to be more dynamic, since the pattern could get larger or smaller.  You mentioned recursion, but is there a formula I could use to build up this latin square.

I posted this question here also, http://stackoverflow.com/questions/18326126/latin-square-algorithm-with-certain-pattern-for-bracket-play

Code: [Select]
public int[,] GetLatinSquare(List<int?> maxPositions)
        {
            var n = maxPositions.Count();

            var latinSquare = new int[n, n];

            for (int i = 0; i < n; i++)
            {
                var maxPosition = maxPositions[i];
                if (maxPosition != null)
                {
                    latinSquare[0, i] = maxPosition.Value;
                }
            }

            for (var i = 0; i < n; i = i+2)
            {
                latinSquare[1, i] = latinSquare[0, i + 1];
                latinSquare[1, i + 1] = latinSquare[0, i];
            }

            for (var i = 0; i < n; i = i + 4)
            {
                latinSquare[2, i] = latinSquare[0, i + 2];
                latinSquare[2, i + 1] = latinSquare[0, i + 3];
                latinSquare[2, i + 2] = latinSquare[0, i + 0];
                latinSquare[2, i + 3] = latinSquare[0, i + 1];
            }

            for (var i = 0; i < n; i = i + 2)
            {
                latinSquare[3, i] = latinSquare[2, i + 1];
                latinSquare[3, i + 1] = latinSquare[2, i];
            }

            return latinSquare;
        }
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: Ian Wakeling on August 20, 2013, 01:24:51 AM
I don't think that you have understood Reply #8 above, which explains how you can start with the order 2 square:

1 2
2 1

and repeatedly double the order to obtain a square as large as you want. At each doubling stage, all entries in the old square are replaced by a 2x2 square, so the new square will have double the number of rows and columns compared to the old.  Each distinct entry in the old square is replaced by a different 2x2 square.  In reply #8, I give all 4 2x2 squares (S1 to S4) that you need to convert the 4x4 square into the 8x8 square.  S1 to S4 are simply the 2x2 square above, where the '1's has been replaced by one member of a seed pair (say 3) and the 2s have been replaced by the other member of the seed pair (say 6).  The whole thing could be implemented recursively if you want.  But note that if you want to go straight to a suitable square of order n, then you could start by using the MOD algorithm to get to an order n/2 square and then double it's size as detailed (will not be the same square as the recursive approach but it will have the properties that you want).  Does that help?

BTW, I have never used any flavour of C, so I have not tried to understand your code, so my apologies if I am missing something here.
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: cblaze22 on August 20, 2013, 12:43:55 PM
I figured it out with your help.  Without you I probably would of never got this done.  Final product below.


Code: [Select]
       public int[,] GetLatinSquare(List<int> maxPositions)
        {
            var n = maxPositions.Count();

            var latinSquare = new int[n, n];

            // Initialize Pattern
            for (int i = 0; i < n; i++)
            {
                latinSquare[0, i] = maxPositions[i];
            }

            var start = 0;
            var startIndex = 1;

            // Start Processing Squares Starting with 2x2
            while ((start = Convert.ToInt32(Math.Pow(2, startIndex))) <= n)
            {
                startIndex++;

                for (int row = 0; row < start/2; row++)
                {
                    var startRow = row;
                    var endRow = start - row - 1;

                    for (var i = 0; i < n; i = i + start)
                    {
                        var startColumn = i;
                        var endColumn = i + start - 1;
                        var columns = endColumn - startColumn + 1;

                        for (var column = 0; column < columns; column++)
                        {
                            latinSquare[endRow, startColumn] = latinSquare[startRow, endColumn];
                            endColumn--;
                            startColumn++;
                        }
                    }
                }
            }

            return latinSquare;
        }
Title: Re: Balance Pool Seeds In Quadrants of Bracket
Post by: aprens on January 03, 2022, 08:26:30 AM
Hi Ian, this post is interesting. How can i apply latin square for this situation?

6 pools and advance top 2 of each pool.

1A 2A
1B 2B
1C 2C
1D 2D

1E 2E
1F 2F

Games should be (in this order):

1A - BYE (no team)
2B - 2C
1D - BYE
1E - 2F
1B - BYE
2A - 2D
1D - BYE
1F - 2E

Thanks.