numの配列を2つの平衡した配列に分割する

Question

私は[[player1, 10], [player2, 8]]のように見えるが、約12人のプレーヤーのような2次元アレイをとる。私はこのメソッドを除いて、私が聞いたソートで十分満足していますteamAは常により良いプレーヤーの "最初の選択"を取得します。私はteamBに一度おいてより良い選手を与える方法を見つけ出すのに苦労しています。以下は、「十分に」機能するコードです。

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); 
    } 
} 

これは私がplayer2とplayer3スイッチチームである好む何teamA: [["player1, 10],["player2", 8]]とteamB: [["player4", 9],["player3", 7]] になります。ここで私が試したことがあります。私の脳で

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

、これはうまく働いたが、すごいことをしませんでしたしている必要があります！私はチームBで9人、チームAで3人で終わった。私は運がないこのアプローチのさまざまなバリエーションを手に入れました。

任意のポインタ？

EDIT：明確にするため、データセットはソートされず、データセットの長さは常に偶数であると仮定できます。他のチームより多くの選手を持つチームは存在しません。

Answer 1

最初にteamAを選択するようにコードを編集した後、teamBを2、teamAを2などを選択します。

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; 
    } 
} 

Answer 2

、ここで説明したように、あなたが取るしたい戦略は、パーティションの問題である：https://en.wikipedia.org/wiki/Partition_problem

あなたは基本的に自分の選手のスコアに基づいて、2つのチームの合計を取りたい、比較現在のプレーヤーをスコアの低いチームに割り当てます。

まず、プレーヤーのデータを並べ替えます。

最初のパスで、チームを無作為に選んでベストプレイヤーを割り当てます。プレイヤープールの残りの部分を反復するとき、私たちはパーティションの問題で説明されているようにアルゴリズムに従います。

私はアクションで、パーティションの問題の一例として、本当に速い何かアウトを書いた：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'); 
    }); 

});