Generating unique matches



  • I've got quite a problem, i've writen a system that needs to generate unique matches within its own pool for as many iterations as possible.

    So for example, let's say my pool looks like

    1
    2
    3
    4

    I will need it to generate

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

    Now with only 4 in the pool this is relativly easy to see and understand, but when you increase the pool, it get's harder and harder to "manualy" solve the matches. Nor have i succeeded in writing code to do this for me reliably and consistent, i'm quite sure this is some sort of mathematical thingy, but i don't know the name for it nor can i find anything about it.

    It would really help me out if someone could give me the name for this or some algorithm to calculate this. My current code only manages to get 30% of the possible matches before it starts to fail finding matches. Now i could brute force the matches but that would take ages on large pools. (currently where talking 500 to 600 nummbers, but this should scale to 1000+ in a few weeks and even more after that.)
     



  • search for permutations / combinations in google



  • [quote user="stratos"]but i don't know the name for it[/quote]

    Sudoku solver? :-P

     



  • Eh? What are you trying to do? To generate all possible variations of the numbers? Are you making a matrix with the combinations? Excuse me for being stupid, but I don't even understand the question...



  • it's not really permutations, since the match has to be unique and for both parties.

    so if 1 matches to 4  then 4 matches to 1, and they both can never match again.
    Permutations work a bit diffrent, since only the whole list of nummbers needs to be unique.

    And yes i've also looked at sudoku, but since the problem there is also quite a bit diffrent it didn't really help.

     

     

     



  • Maybe a few more examples might help, I've re-read your posts a few times and still can't understand what you are after.

     For instance what is wrong with:-

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

    as an alternative to the solution you posted? 



  • mmm wel i'm terrible at explaining :) so i'll just try it indeed by example.

     What's wrong with your example is that the matches don't go both ways.



    if 1 matches to 2, 2 must match to 1.

    so let's say we have the following pool

     
    1
    2
    3
    4
    5
    6

    Then the first iteration of the program te following matches should be made
    let's match
    1 to 6
    2 to 5
    3 to 4

      1st
    1 6
    2 5
    3 4
    4 3
    5 2
    6 1

    ok second loop
    let's match
    1 to 5
    2 to 4
    3 to 6

      1st 2nd
    1 6 5
    2 5 4
    3 4 6
    4 3 2
    5 2 1
    6 1 3

    now for the third loop

    let's match
    1 to 4
    2 to 3
    5 to 6

      1st 2nd 3rd
    1 6 5 4
    2 5 4 3
    3 4 6 2
    4 3 2 1
    5 2 1 6
    6 1 3 5

    now the fourth loop

    1 to 3
    2 to 6
    4 to 5

      1st 2nd 3rd 4th
    1 6 5 4 3
    2 5 4 3 6
    3 4 6 2 1
    4 3 2 1 5
    5 2 1 6 4
    6 1 3 5 2

    fifth loop

    1 to 2
    3 to 5
    4 to 6

      1st 2nd 3rd 4th 5th
    1 6 5 4 3 2
    2 5 4 3 6 1
    3 4 6 2 1 5
    4 3 2 1 5 6
    5 2 1 6 4 3
    6 1 3 5 2 4


    Now no more matches can be made.

    As you can see matches go both ways and only occur once.
     



  • [quote user="stratos"]Then the first iteration of the program te following matches should be made
    let's match
    1 to 6
    2 to 5
    3 to 4
    [/quote]

    Does it matter what order the "matches" are made in? So would it be ok to do 1 to 5,2 to 4,3 to 6 in the first round instead?


    Isn't the choosing of the "mappings" just combinations of 2 from a pool of 6? (forget that)

    Couldn't you just use a 2d array to keep track of what mappings you've used and use it to generate the next set until no more are possible? 



  • indeed it doesn't really matter what a nummber matches too as long as it's "legal"

    but i was hoping someone would know this problem and would point me in the right direction, since i have the suspicion that this is some sort of known mathematical thingy. (since i already figured it looked so much like permutations, but the formulas associated with those can't really be applied to this, nor am i able to adapt them to apply to this)



     



  • Try backtracking?

    Anyway, how is this not like nCr? 

    Whatever your trying to do, look into recursion and dynamic programming.  



  •  

      1st 2nd 3rd 4th 5th
    1 6 5 4 3 2
    2 5 4 3 6 1
    3 4 6 (2 1) 5
    4 3 (2 1) 5 6
    5 (2 1) 6 4 3
    6 1 3 5 2 4

    Isn't that an illegal sollution?  I put brackets around 3 matches that are the same. Or am I just not getting the problem?

    it seems like dynamic programming problem but I'm not quite sure it is. Maybe try to figure out how to make 6 disjoint functions from with input and output the numbers within your pool? 



  • I suspect you need something along the lines of

    http://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_Algorithm ?



  • the matrix is just a representation of the matchings.
    I don't care if there is some 'hidden' pattern in the matches, just as long as all matches are unique and go both ways. (if 1 matches 5, 5 matches 1)

     
    the round robin thing is almost precisly what i am looking for. it's not a complete answer to my problem, but that would be impossible since i also need to have some special restrictions and conditions.

    this is because the numbers also have some preferences as to which other numbers they would want to match first. 

     But i'll certainly read up on it.
     

     



  • [quote user="stratos"]

    this is because the numbers also have some preferences as to which other numbers they would want to match first. 

    [/quote]

    Is this preference easy to explain? I was under the impression that there wasn't any preference.

     I'm fairly certain I can code what you are asking for without back tracking, etc. I'll have a go tomorrow if I get a spare moment.
     



  • well the most important preference is that of region.

     there are 3 types of regions.

    international, country, province.

    each number resides in the province of a country, and has a matching preference to some region.
    So for instance number 1 could reside in south belgium, and want to match with people from the benelux.

    2 resides in the south belgium and wants to match with someone in south belgium.
    3 resides in east germany and wants to match with someone in the benelux.

    1 will want to match 3
    2 will want to match 1.
    3 will also want to match 1.

    Now the preference should also look for lesser candidates if he can't find his prefered preference.

    for instance 2 wanted to match south belgium, if we can't find anyone in south belgium for him to match with, we look to it's parent the country belgium to match with. If we can't find a match in belgium we look for its parent 'benelux' then europe then worldwide.

    This is all hierachically set in a database with the following structure.
    id      int(3)
    name     varchar(255)
    type     enum('province', 'country', 'international')
    parent_id     int(3)

     



  • [quote user="stratos"]

    I've got quite a problem, i've writen a system that needs to generate unique matches within its own pool for as many iterations as possible.

    So for example, let's say my pool looks like

    1
    2
    3
    4

    I will need it to generate

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

    Now with only 4 in the pool this is relativly easy to see and understand, but when you increase the pool, it get's harder and harder to "manualy" solve the matches. Nor have i succeeded in writing code to do this for me reliably and consistent, i'm quite sure this is some sort of mathematical thingy, but i don't know the name for it nor can i find anything about it.

    It would really help me out if someone could give me the name for this or some algorithm to calculate this. My current code only manages to get 30% of the possible matches before it starts to fail finding matches. Now i could brute force the matches but that would take ages on large pools. (currently where talking 500 to 600 nummbers, but this should scale to 1000+ in a few weeks and even more after that.)
     

    [/quote]

    Here is a very quick and dirty algorithm (in Java) that (I think) generates a matrix of pairings to your specifications.  I won't do much analysis of its efficiency.   :P

    It works by starting at position 0,0 and moving left to right, top to bottom, and finding the lowest number that doesn't already exist to the left of, or above, the current position.  When it finds such a number, it stores it at the current location, and at the mirrored location in the matrix.  When going from left to right in each row, it starts past the point where it knows the result has already been mirrored.  If you trace through it, you will see how it works, and probably will be able make many improvements to it if you want to add some kind of 'preferred matching' type stuff.

    public class Pairs {
        public static void main(String[] args) {
            new Pairs().test();
        }

        public void test() {
            int[][] arr = buildArray(8);
            for (int row = 0; row < arr.length; row++) {
                for (int col = 0; col < arr[row].length; col++) {
                    System.out.print(arr[row][col] + "  ");
                }
                System.out.println();
            }
        }

        private int[][] buildArray(int size) {
            int arr[][] = new int[size][size];

            for (int row = 0; row < size; row++) {
                for (int col = row; col < size; col++) { // start to the left of where the mirrored results already exists
                    int test = 1;
                    while (left(arr, test, row, col) || above(arr, test, row, col)) {
                        test++;
                    }
                    arr[row][col] = test;
                    arr[col][row] = test;
                }
            }

            return arr;
        }

        private boolean above(int[][] arr, int test, int row, int col) {
            for (int x = 0; x < row; x++) {
                if (arr[x][col] == test)
                    return true;
            }
            return false;
        }

        private boolean left(int[][] arr, int test, int row, int col) {
            for (int x = 0; x < col; x++) {
                if (arr[row][x] == test)
                    return true;
            }
            return false;
        }
    }

    Output:

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

     



  • [quote user="CodeRage"][quote user="stratos"]

    I've got quite a problem, i've writen a system that needs to generate unique matches within its own pool for as many iterations as possible.

    So for example, let's say my pool looks like

    1
    2
    3
    4

    I will need it to generate

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

    Now with only 4 in the pool this is relativly easy to see and understand, but when you increase the pool, it get's harder and harder to "manualy" solve the matches. Nor have i succeeded in writing code to do this for me reliably and consistent, i'm quite sure this is some sort of mathematical thingy, but i don't know the name for it nor can i find anything about it.

    It would really help me out if someone could give me the name for this or some algorithm to calculate this. My current code only manages to get 30% of the possible matches before it starts to fail finding matches. Now i could brute force the matches but that would take ages on large pools. (currently where talking 500 to 600 nummbers, but this should scale to 1000+ in a few weeks and even more after that.)
     

    [/quote]

    Here is a very quick and dirty algorithm (in Java) that (I think) generates a matrix of pairings to your specifications.  I won't do much analysis of its efficiency.   :P

    It works by starting at position 0,0 and moving left to right, top to bottom, and finding the lowest number that doesn't already exist to the left of, or above, the current position.  When it finds such a number, it stores it at the current location, and at the mirrored location in the matrix.  When going from left to right in each row, it starts past the point where it knows the result has already been mirrored.  If you trace through it, you will see how it works, and probably will be able make many improvements to it if you want to add some kind of 'preferred matching' type stuff.

    public class Pairs {
        public static void main(String[] args) {
            new Pairs().test();
        }

        public void test() {
            int[][] arr = buildArray(8);
            for (int row = 0; row < arr.length; row++) {
                for (int col = 0; col < arr[row].length; col++) {
                    System.out.print(arr[row][col] + "  ");
                }
                System.out.println();
            }
        }

        private int[][] buildArray(int size) {
            int arr[][] = new int[size][size];

            for (int row = 0; row < size; row++) {
                for (int col = row; col < size; col++) { // start to the left of where the mirrored results already exists
                    int test = 1;
                    while (left(arr, test, row, col) || above(arr, test, row, col)) {
                        test++;
                    }
                    arr[row][col] = test;
                    arr[col][row] = test;
                }
            }

            return arr;
        }

        private boolean above(int[][] arr, int test, int row, int col) {
            for (int x = 0; x < row; x++) {
                if (arr[x][col] == test)
                    return true;
            }
            return false;
        }

        private boolean left(int[][] arr, int test, int row, int col) {
            for (int x = 0; x < col; x++) {
                if (arr[row][x] == test)
                    return true;
            }
            return false;
        }
    }

    Output:

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

     

    [/quote]

    Wow, scrap this, it doesn't work for all sizes.  What are the odds the two sizes I ran as tests both were ones that worked?  Anyway, I wrote this very fast, and should have put more thought into it. 



  • What you are trying to do is to find all possible ways to divide your pool (which has to have an even number of elements) into pairs.

    A bit of math tells you that there are for n elements in your set, your program has to consider n!/((n/2)! * 2^(n/2)) possible arrangements.

    Note that this number is larger than (n/2-1)!*2^(n/2-1);  for a set of 1000 elements, this means it's larger then 499!*2^499.

    I'm afraid no algorithm, no matter how clever, will finish that till the end of the universe.
     

     



  • [quote user="ammoQ"]

    What you are trying to do is to find all possible ways to divide your pool (which has to have an even number of elements) into pairs.

    A bit of math tells you that there are for n elements in your set, your program has to consider n!/((n/2)! * 2^(n/2)) possible arrangements.

    Note that this number is larger than (n/2-1)!*2^(n/2-1);  for a set of 1000 elements, this means it's larger then 499!*2^499.

    I'm afraid no algorithm, no matter how clever, will finish that till the end of the universe.
     

     

    [/quote]

    Actually, it seems he is trying to generate a NxN matrix, filled with numbers 1 through N, where no number appears in the same row or column more than once.  The algorithm I gave seems to work for powers of two, and I wrote it without a whole lot of thought and didn't spend much time at it, and my test cases 4 and 8 worked.  This is basically a matrix of a round robin schedule, where the first column represents the player number, columns 2-N represent each round, where the data gives the

    I am sure there is a fairly efficient and systematic way of generating such a matrix.  Anyway, I tried, and don't have much more time to think about this...



  • [quote user="stratos"]

    I've got quite a problem, i've writen a system that needs to generate unique matches within its own pool for as many iterations as possible.

    So for example, let's say my pool looks like

    1
    2
    3
    4

    I will need it to generate

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

    Now with only 4 in the pool this is relativly easy to see and understand, but when you increase the pool, it get's harder and harder to "manualy" solve the matches. Nor have i succeeded in writing code to do this for me reliably and consistent, i'm quite sure this is some sort of mathematical thingy, but i don't know the name for it nor can i find anything about it.

    It would really help me out if someone could give me the name for this or some algorithm to calculate this. My current code only manages to get 30% of the possible matches before it starts to fail finding matches. Now i could brute force the matches but that would take ages on large pools. (currently where talking 500 to 600 nummbers, but this should scale to 1000+ in a few weeks and even more after that.)
     

    [/quote]

    This works for all EVEN sizes.  For odd pairings, add one to the size and use that number as a bye.  There is probably a way to remove the data array and combine the two inner loops, but I think this is easier to understand.  It uses the cyclical technique of round-robin scheduling.

    public class Pairs {
        public static void main(String[] args) {
            new Pairs().test();
        }

        public void test() {
            int[][] arr = buildArray(4);
            for (int row = 0; row < arr.length; row++) {
                for (int col = 0; col < arr[row].length; col++) {
                    System.out.printf("%4d", arr[row][col]);
                }
                System.out.println();
            }
        }

        private int[][] buildArray(int size) {
            int[][] arr = new int[size][size];
            int[] data = new int[size];

            data[0] = 1;
            for (int row = 0; row < size; row++) {
                arr[row][0] = row + 1;
            }
            for (int col = 1; col < size; col++) {
                int position = col;
                int value = 2;
                while (value <= size) {
                    data[position] = value++;
                    if (++position == size)
                        position = 1;
                }
                for (int row = 0; row < size / 2; row++) {
                    int a = data[row];
                    int b = data[size - row - 1];
                    arr[a - 1][col] = b;
                    arr[b - 1][col] = a;
                }
            }
            return arr;
        }
    }



  • [quote user="CodeRage"][quote user="ammoQ"]

    What you are trying to do is to find all possible ways to divide your pool (which has to have an even number of elements) into pairs.

    A bit of math tells you that there are for n elements in your set, your program has to consider n!/((n/2)! * 2^(n/2)) possible arrangements.

    Note that this number is larger than (n/2-1)!*2^(n/2-1);  for a set of 1000 elements, this means it's larger then 499!*2^499.

    I'm afraid no algorithm, no matter how clever, will finish that till the end of the universe.
     

     

    [/quote]

    Actually, it seems he is trying to generate a NxN matrix, filled with numbers 1 through N, where no number appears in the same row or column more than once.  The algorithm I gave seems to work for powers of two, and I wrote it without a whole lot of thought and didn't spend much time at it, and my test cases 4 and 8 worked.  This is basically a matrix of a round robin schedule, where the first column represents the player number, columns 2-N represent each round, where the data gives the

    I am sure there is a fairly efficient and systematic way of generating such a matrix.  Anyway, I tried, and don't have much more time to think about this...

    [/quote] Aahh yes, I see your point.

    I think the real task is: "Find all possible pairs. (The number of possibe pairs is n*(n-1); add an index column and you get a nice n*n matrix). Show them in a matrix where the first columns is 1..n and the other columns show some arrangements of those pairs, so that no number appears twice in the same row or column and  some kind of symmetry takes place:  If the value in the row n is x, then the value in row x shall be n.

    Anyway, I don't see a legitimate use for that in any real world problem. For a brute force optimization, the n!/((n/2)! * 2^(n/2)) method is the way to go.

    Note that though your algorithm produces valid results (by the specification above), there are other, valid results too.

    For example, for n=6, your algorithm produces:

    1 6 5 4 3 2

    2 5 3 6 4 1

    3 4 2 5 1 6

    4 3 6 1 2 5

    5 2 1 3 6 4

    6 1 4 2 5 3

    Another possible correct result would be:

    1 6 5 4 3 2

    2 4 6 3 5 1

    3 5 4 2 1 6

    4 2 3 1 6 5

    5 3 1 6 2 4

    6 1 2 5 4 3

    i A B C D E

     

    This result is significantly different from your result; you cannot simply get it by permuting the columns of your result. To see the significance of the difference, let's pretend that all numbers represent persons; 1 loves 6, 2 loves 4 and 3 loves 5. All other combinations are hate. Let's say love scores +1 and hate -1.

    The score of column A is 3, while B,C,D and E have a score of -3. In your matrix, columns A, C and D have a score of -1, B and E have -3.

    In other words, the method implemented in your algorithm is not sufficient to find the optimal result (which is what the OP is looking for, I assume), if only the score of whole columns is considered. This is not a fault in your algorithm (which is really well done!), it's a flaw in the original specification.



  • [quote user="ammoQ"][quote user="CodeRage"][quote user="ammoQ"]

    What you are trying to do is to find all possible ways to divide your pool (which has to have an even number of elements) into pairs.

    A bit of math tells you that there are for n elements in your set, your program has to consider n!/((n/2)! * 2^(n/2)) possible arrangements.

    Note that this number is larger than (n/2-1)!2^(n/2-1);  for a set of 1000 elements, this means it's larger then 499!2^499.

    I'm afraid no algorithm, no matter how clever, will finish that till the end of the universe.
     

     

    [/quote]

    Actually, it seems he is trying to generate a NxN matrix, filled with numbers 1 through N, where no number appears in the same row or column more than once.  The algorithm I gave seems to work for powers of two, and I wrote it without a whole lot of thought and didn't spend much time at it, and my test cases 4 and 8 worked.  This is basically a matrix of a round robin schedule, where the first column represents the player number, columns 2-N represent each round, where the data gives the

    I am sure there is a fairly efficient and systematic way of generating such a matrix.  Anyway, I tried, and don't have much more time to think about this...

    [/quote] Aahh yes, I see your point.

    I think the real task is: "Find all possible pairs. (The number of possibe pairs is n(n-1); add an index column and you get a nice nn matrix). Show them in a matrix where the first columns is 1..n and the other columns show some arrangements of those pairs, so that no number appears twice in the same row or column and  some kind of symmetry takes place:  If the value in the row n is x, then the value in row x shall be n.

    Anyway, I don't see a legitimate use for that in any real world problem. For a brute force optimization, the n!/((n/2)! * 2^(n/2)) method is the way to go.

    Note that though your algorithm produces valid results (by the specification above), there are other, valid results too.

    For example, for n=6, your algorithm produces:

    1 6 5 4 3 2
    2 5 3 6 4 1
    3 4 2 5 1 6
    4 3 6 1 2 5
    5 2 1 3 6 4
    6 1 4 2 5 3

    Another possible correct result would be:

    1 6 5 4 3 2
    2 4 6 3 5 1
    3 5 4 2 1 6
    4 2 3 1 6 5
    5 3 1 6 2 4
    6 1 2 5 4 3
    i A B C D E
     

    This result is significantly different from your result; you cannot simply get it by permuting the columns of your result. To see the significance of the difference, let's pretend that all numbers represent persons; 1 loves 6, 2 loves 4 and 3 loves 5. All other combinations are hate. Let's say love scores +1 and hate -1.

    The score of column A is 3, while B,C,D and E have a score of -3. In your matrix, columns A, C and D have a score of -1, B and E have -3.

    In other words, the method implemented in your algorithm is not sufficient to find the optimal result (which is what the OP is looking for, I assume), if only the score of whole columns is considered. This is not a fault in your algorithm (which is really well done!), it's a flaw in the original specification.

    [/quote]

    The real world use is to generate a schedule for a round-robin style tournament.  The matrix shows which players compete each round.  You can easily see why each number can only appear once in each row, and once in each column (a player can't play in two games in the same round, and no player should face the same opponent more than once).  Also note that if player N competes with player M in a round, the matrix shows player N competing with M in the same round.

    Opponent
    Player#Round 1Round 2Round 3Round 4Round 5
    165432
    253641
    342516
    436125
    521364
    614253

    There are many other matrices that solve this problem, but I don't see why any particular matrix would be better than another given this usage.  (Of course I'm not 100% certain this is the usage the original poster had in mind)



  • You are right with the schedule for the round-robin tournament, but looking at Post 97729, I doubt that this is what the OP was thinking of.



  • Sorry for the late reply, but indeed this is more of a match making principle then 'tournament'

    i still have to read the last few posts a bit to understand it, but it only occurs to me now that there is a fundemental point that breaks it all. (i think)

    in the realworld application of this, the number of numbers getting matched isn't fixed.

    so on the first matching we might match numbers 1,2,3,4,5 and on the second instance 2 might have left and 6 and 7 might have joined.

    So the second iteration we might have to match 1,3,4,5,6,7

     
    And reading between the lines of ammoQ's post, no sorry :) this isn't for a dating site.
    but it is a similair concept though.
     



  • [quote user="stratos"]

    Sorry for the late reply, but indeed this is more of a match making principle then 'tournament'

    i still have to read the last few posts a bit to understand it, but it only occurs to me now that there is a fundemental point that breaks it all. (i think)

    in the realworld application of this, the number of numbers getting matched isn't fixed.

    so on the first matching we might match numbers 1,2,3,4,5 and on the second instance 2 might have left and 6 and 7 might have joined.

    So the second iteration we might have to match 1,3,4,5,6,7

     
    And reading between the lines of ammoQ's post, no sorry :) this isn't for a dating site.
    but it is a similair concept though.
     

    [/quote]

    I really think you need to specify this problem better.  (1,2,3,4,5) has an odd number of elements, so how do you pair each one for "iteration 1"?  What exactly is an iteration?  And if number(s) can be added or removed between iteration, how do you prevent numbers from being paired more than once?  From your examples, every one of them was an NxN matrix with no number appearing twice in a row or twice in a column.  But if you keep changing what numbers are in the set, as well as the size of the set, I don't see what you would end up with in the end.



  • I'm still not sure the problem has been adequately defined.

    What exactly defines a match? Is a "match" a unique pair of numbers from a pool? That would be combinations (n over k and such claptrap). But it's not quite like that, as the obviously is a matrix involved.

    Vague problems have no solution.
    Clear problems provide their solution by virtue of being stated.

    in the realworld application of this, the number of numbers getting matched isn't fixed.

    So the second iteration we might have to match 1,3,4,5,6,7


    This is not likely to pose a problem. If you store the numbers in an array, you can ensure that the array is dense and in order, regardless of the values of the elements.


Log in to reply