I need an efficient algorithm for best matching

Question

2.00/5 (2 votes)

See more:

I have, for instance, 10 teams and I need to match them.

Criteria are;

1 - Two teams are matched only one time.
2 - Teams with closest points must be matched.

It could be iterated 9 (n-1) times max and this is what I try to do, go further as I can.

At the end of each iteration, points of teams increase randomly.

I populated my list with random data.

C#

List<Team>  _teams = new List<Team>();

for (int i = 1; i <= 10; i++)
{
  _teams.Add(new Team("Team "+i,MyExtensions.RandomNumber(31)));
}

private static readonly Random Rand = new Random();

public static int RandomNumber(int max)
{
  return Rand.Next(max);
}

My team class;

C#

public class Team
{
    private string _name;
    private double _point;
    private List<Team> _matchedTeams;
    private Team _currentMatch;

    public Team CurrentMatch
    {
        get { return _currentMatch; }
        set { _currentMatch = value; }
    }

    public List<Team> MatchedList
    {
        get { return _matchedTeams; }
        set { _matchedTeams = value; }
    }

    public string Name
    {
        get { return _name; }
        set { _name = value; }
    }

    public double Point
    {
        get { return _point; }
        set { _point = value; }
    }

   public Team(string name, double point)
    {
        _matchedTeams = new List<Team>();
        _name = name;
        _point = point;
    }

    public override string ToString()
    {
        return _name + " - (" + _point + ")";
    }
}

And here's my extension method to get closest match;

C#

public static Team FindClosest(this List<Team> list, Team team)
{
    var orderedItems =
        list.Where(p => p != team && !p.MatchedList.Contains(team)).OrderBy(x => Math.Abs(x.Point - team.Point));
    return orderedItems.FirstOrDefault();
}

  var nearestMatch = _teams.FindClosest(_teams.ElementAt(0));

I prefer an algorithm like backtracking instead of brute force or random trial-and-error.

Can you suggest me an algorithm, a method to solve my problem?

Any help would be much appreciated.
Thank you.

Posted 24-Apr-14 9:59am

Emre Ataseven

Updated 24-Apr-14 10:43am

v3

Add a Solution

Comments

Sergey Alexandrovich Kryukov 24-Apr-14 16:36pm

Sorry, this is not a question...
—SA

Emre Ataseven 24-Apr-14 16:42pm

I need an algorithm, a method, a way to solve my problem, can you help me? Is it question now?

BillWoodruff 26-Apr-14 1:54am

Not clear if you are modeling a real-world competition. Is this a contest where after each match the "loser" is eliminated from the pool of teams ? One-game-at-a-time contest, or contest starts with five simultaneous matches ?

"At the end of each iteration, points of teams increase randomly." Why ?

Emre Ataseven 27-Apr-14 4:49am

No elemination, each team will play each team one time. And we are trying to simulate this scenario, is it possible to know which team will win now? So we are increasing scores randomly. But you are persisting you can increase points constant.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Matt T Heffron · Answer 1 · 2014-04-24T10:35:00

Solution 1

Why not just sort the list by Point value and then take them 2 at a time.
By sorting, the closest values will be adjacent.

Posted 24-Apr-14 10:35am

Matt T Heffron

Comments

Emre Ataseven 24-Apr-14 16:37pm

Yes, it works for first iteration. But for next iterations "Two teams are matched only one time." criterion disables this method.

Matt T Heffron 24-Apr-14 16:40pm

OK, I misunderstood the iteration part of the problem.

D Sarthi Maheshwari · Answer 2 · 2014-11-24T09:56:00

As far as I understood, you are going to have 9! games with 10 teams as sooner or later each team will play a match with others.
I noticed that in your algorithm you are using

C#

for (int i = 1; i <= 10; i++)
 {
   _teams.Add(new Team("Team "+i,MyExtensions.RandomNumber(31)));
 }

If space complexity is not a problem, currently, I suggest following:
0. Create an array of HashSet (size = n-1, in your case 9). In these hashsets, we will keep the team_number with which the team_index has player a match. (Note: When there is a match between team 4 and 5, we do arrayHashset[4].add(5) and we never do arrayHashset[HighNumber].add(SmallerNumber) because this entry will be avilable to us in arrayHashset[SmallNumber].add(HighNumber).
1. The index of this array is the team number, 1 - 9 (Team 10 wont have any hashset as its the highest number thus all matches of team 10 will be saved in other hashsets).
2. Sort the list during the above loop.
3. Take first two of this list and make a match. Whichever number is smaller. Do ArrayHashSet[SmallerNumber].add(greaterNumber).
4. Increase the points randomly, sort it. Take above two, find min of those team. Look in the hashset of min number if the higher number is present or not. If not make the match else choose the team in sorted array which is just below and repeat again.

Two minor optimization you can do is:
1. Eliminate a team from the list once it has played matches against all other teams this would reduce the sorting complexity a bit for remaining matches. You can maintain an array to keep the match counter indexed by the team_number.
2. When you increase the points randomly, if possible, first increase points of the team which is at 0th index in the latest sorted list, then 1st index, then 2nd and so on... By doing so, you have the opportunity to check if after increasing points this team is eligible for index change or not (thus you can avoid unnecessary moves for sorting).

Right now, I am unable to think of any other solution. Hope you would post me back some better solution once found.