Divide array of nums into 2 balanced arrays

Question

I'm take a 2d array that looks something like [[player1, 10], [player2, 8]] but with around 12 players. I'm satisfied enough with the sorting I have hear, except with this method teamA always gets the "first pick" of the better player. I am struggling to figure out a way to give teamB the better player every other time. below is the code as is that works "well enough".

data = [["player1", 10]. ["player2", 8], ["player3", 7], ["player4", 9]];
var teamA = [];
var teamB = [];

var remaining = [];

for (item in data) {
  remaining.push(data[item].slice());
}

for (i in data) {
  var max = 0;
  var selection = [,];
  var index = -1;

  for (k in remaining) {
    if (remaining[k][1] > max) {
      selection =  remaining[k];
      max = remaining[k][1];
      index = k;
    }
  }
  remaining.splice(index, 1);

  if (i % 2 == 0) {
    teamA.push(selection);
  } else {
    teamB.push(selection);
  }
}

This results in teamA: [["player1, 10],["player2", 8]] and teamB: [["player4", 9],["player3", 7]] What I would prefer is player2 and player3 switch teams. Here's what I tried.

// inside my first for loop
if (3 % i == 0) {
  i++;
} else if (4 % i == 0) {
  i--;
}

In my brain, this should have worked just fine but wow did it not! I ended up with like 9 players on teamB and 3 on teamA. I fiddled with different variations of this approach with no luck.

Any pointers?

EDIT: For clarification, it can be assumed the data set will be unsorted coming in, and that the length of the data set will always be even. There won't be a team with more players than the other.

Does your player data arrive in sorted order? (sorted by player point) — thenormalsquid, May 12 '17 at 21:47
Should the teams be _exactly_ even in terms of number of players or is it ok for Team A to have 3 players and Team B to have 4? — thenormalsquid, May 12 '17 at 21:55
Using for...in for iterating array is bad practice http://stackoverflow.com/questions/500504/why-is-using-for-in-with-array-iteration-a-bad-idea — hoangfin, May 12 '17 at 22:15
@MeteorZero Interesting. Welp, another reason for me to hate javascript I guess. :) — jtsmith1287, May 12 '17 at 22:42
Yep, you could use forEach: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/forEach?v=example or just a regular for loop construct. — thenormalsquid, May 12 '17 at 22:44

score 0 · Answer 1 · answered May 12 '17 at 22:11

I have edited your code so that it will choose first for teamA, then it will choose 2 for teamB, then 2 for teamA and so on.

var data = [
    ["player1", 10],
    ["player2", 8],
    ["player3", 7],
    ["player4", 9],
    ["player5", 5],
    ["player6", 6]
];
var teamA = [];
var teamB = [];

var remaining = [];

for (item in data) {
    remaining.push(data[item].slice());
}

var turnA = false;
var counterA = 0,
    counterB = 0;
for (i in data) {
    var max = 0;
    var selection = [, ];
    var index = -1;

    for (k in remaining) {
        if (remaining[k][1] > max) {
            selection = remaining[k];
            max = remaining[k][1];
            index = k;
        }
    }
    remaining.splice(index, 1);

    // add first player to teamA and continue
    if (i == 0) {
        teamA.push(selection);
        continue;
    }

    if (turnA) {
        teamA.push(selection);
        counterA++;
    } else {
        teamB.push(selection);
        counterB++;
    }

    if (turnA && counterA == 2) {
        counterA = 0;
        turnA = false;
    } else if (!turnA && counterB == 2) {
        counterB = 0;
        turnA = true;
    }
}

score 0 · Answer 2 · answered May 12 '17 at 22:42

So, the strategy you want to take is the partition problem, as described here: https://en.wikipedia.org/wiki/Partition_problem

You basically want to take the sum of the two teams, based on their players' scores, compare the sum, and assign the current player to the team with the lesser score.

First, we sort the player data.

At the first pass, we randomly select a team to assign the best player. As iterate through the rest of the player pool, we follow the algorithm as described in the partition problem.

I wrote something out really quick as an example of the partition problem in action: https://codepen.io/thenormalsquid/pen/Lymjbb?editors=0001

// stack overflow answer


var data = [["player1", 10], ["player2", 8], ["player3", 7], ["player4", 9]];
var teamA = [];
var teamB = [];
var selectionProbability = 0.5;

var remaining = [];

data.sort(function(playerA, playerB){
    if(playerA[1] < playerB[1]) {
    return 1;
  }

  if(playerA[1] > playerB[1]) {
    return -1;
  }

  return 0;
});

var sum = function(team) {
  if (team.length === 0) {
    return 0;
  }
  var i,
      s = 0;
  for(i = 0; i < team.length; i++) {
    s += team[i][1];
  }
  return s;
};

var chooseTeam = function() {
  if(Math.random() < selectionProbability) {
    return 'teamA';
  }
  return 'teamB';
};


function assignTeams() {
  var i;
  for(i = 0; i < data.length; i++) {
    var sumA = sum(teamA),
        sumB = sum(teamB);
    // first pass, we'll have a 50/50 chance 
    // of placing the best player in either team A or team B

    if (i === 0) {
      var chosenTeam = chooseTeam();
      if (chosenTeam === 'teamA') {
        teamA.push(data[i]);
      } else {
        teamB.push(data[i]);
      }
    } else if (sumA < sumB) {
      teamA.push(data[i]);
    } else {
      teamB.push(data[i]);
    }
  }
}

function addPlayerToHtml(player, teamId) {
  var li = document.createElement('li'),
      text = document.createTextNode(player[0] + ' ' + player[1]);
  li.appendChild(text);
  document.getElementById(teamId).appendChild(li);
}

var button = document.getElementById('assignPlayers');
button.addEventListener('click', function(){
  assignTeams();

  teamA.forEach(function(player){
    addPlayerToHtml(player, 'teamA');
  });

  teamB.forEach(function(player){
    addPlayerToHtml(player, 'teamB');
  });

});

Divide array of nums into 2 balanced arrays

2 Answers2