Algorithm for a team generator

Question

I have created a random team generator with Javascript and it works to generate two random teams of five players each. This is how it looks :

and I created a function to determine the value of each rank :

function getRankValue(rank) {
let rankValue;

    switch(rank) {
        case "platinum1" : rankValue = 2100;
        break;

        case "platinum2" : rankValue = 2000;
        break;

        case "platinum3" : rankValue = 1900;
        break;

        case "platinum4" : rankValue = 1800;
        break;

        case "gold1" : rankValue = 1650;
        break;

        case "gold2" : rankValue = 1550;
        break;

        case "gold3" : rankValue = 1450;
        break;

        case "gold4" : rankValue = 1350;
        break;

        case "silver1" : rankValue = 1200;
        break;

        case "silver2" : rankValue = 1100; 
        break;

        case "silver3" : rankValue = 1000;
        break;

        case "silver4" : rankValue = 900;
        break;

        case "bronze1" : rankValue = 750;
        break;

        case "bronze2" : rankValue = 650; 
        break;

        case "bronze3" : rankValue = 550;
        break;

        case "bronze4" : rankValue = 450;
        break;

        case "iron1" : rankValue = 300;
        break;

        case "iron2" : rankValue = 200;
        break;

        case "iron3" : rankValue = 100;
        break;

        case "iron4" : rankValue = 0;
        break;
    }

    return rankValue;

I want to make the generator create teams based on the players rank value to create a balanced total team value. For example :

4x Silver4(900 value each) & 1x bronze 4 (450 value) for a total value of 4050 versus :

3x Silver1(1200 value each) & 2x iron2(200 value each) for a total value of 4000. I want to make it have some room for +- 200 value, otherwise it would be too complex.

How should the algorithm look like?

I want to make sure to understand well your question. You start with a team of value N and you want to randomly generate a team of value N +/- 200? — Cid, Dec 11 '21 at 14:58
Yes that is correct. A total of 10 players will be placed in two different teams and both teams should have a balanced total team value. — Ruthless, Dec 11 '21 at 15:00
So, it's different from my understanding, you want to generate both teams together so their value match — Cid, Dec 11 '21 at 15:02
Sorry I misread your comment, yes both teams together so their values are balanced against eachother — Ruthless, Dec 11 '21 at 15:03
This is the `Balanced number partitioning` problem (see https://en.wikipedia.org/wiki/Balanced_number_partitioning), specifically the variant `Two-way balanced partitioning`. See also `Two way partitioning` at https://en.wikipedia.org/wiki/Largest_differencing_method. If the number of players will always be relatively small, then you can boil this down to a brute force combinatorics problem. Ie, every combination of 5 players from a pool of 10, seeking the minimal difference of the residual 5 players... — Trentium, Dec 11 '21 at 17:34
As a follow up, here's a link to a slew of algorithms that generate combinations of k elements from n objects... https://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n — Trentium, Dec 11 '21 at 17:47

Trentium · Accepted Answer · 2021-12-13T13:27:06.250

Here is a solution based on generating all combinations. Note that balanced number partitioning and two way partitioning have a number of practical solutions. The solution presented here makes use of a brute force evaluation of all combination of 5 players.

Using a python combination function as reference, the Javascript version of the combinations iterator function below churns out combinations of 5 players from the provided list of 10 player rankings. The overall solution is brute force, in that it iterates over all combinations of 5 players, and returns the best combination of players based on the least difference in team values.

function *combinations( combo, list, k ) {
  if ( k == 0 ) {
    yield combo;
  } else {
    for ( let i = 0; i < list.length; i++ ) {
      yield *combinations( [...combo, list[ i ] ], list.slice( i + 1 ), k - 1 ); 
    }
  }
}


let players = [ 1200, 1200, 1200, 900, 900, 900, 900, 450, 200, 200 ];
let playersTotal = players.reduce( ( sum, player ) => sum += player, 0 );

let team1 = combinations( [], players, 5 );

let nextCombo;
let minCombo, minDiff = Number.MAX_SAFE_INTEGER;

do {
  nextCombo = team1.next().value;
if ( nextCombo == null ) break;
  let team1Sum = nextCombo.reduce( ( sum, player ) => sum += player, 0 );
  let diff = Math.abs( ( playersTotal - team1Sum ) - team1Sum );
  if ( diff < minDiff ) {
    minCombo = nextCombo;
    minDiff = diff;
  }
  if ( diff <= 200 ) {
    console.log( `Team: ${nextCombo.join( ',' )}, Total: ${team1Sum}, Diff: ${diff}` );
  }
} while ( true );

console.log( `Best matchup is Team 1 of ${minCombo} with diff of ${minDiff}` );

Note that the use of an iterator function to churn out combinations has the advantage of terminating the request for further combinations if satisfied with the most recent result. This also has the benefit that if searching for larger teams, where computing all combinations is impractical, a timer can be added to the loop which fetches the next team combination, and the best result can be used after the timer is up, so as to limit the search time. In such a case, it will be prudent to randomly shuffle the player list prior to calling combinations so that the combinations generated are not all heavily loaded with the best players, giving a better chance at obtaining a balanced pairing of teams...

Thank you for this extended answer, I will try to apply the same logic in javascript — Ruthless, Dec 13 '21 at 11:26
@Ruthless just a note that the code snippet is in Javascript. I simply used the Python reference as a source for the `combinations` algorithm. — Trentium, Dec 13 '21 at 13:26

Algorithm for a team generator

1 Answers1