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?

CodePudding user response：

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...