Algorithm to form two teams from a list of 10 people based on skillindex

Question

I am trying to come up with an algorithm that checks all possible combinations in a list of players and makes two teams of 5 with the closest possible difference in total skillIndex. So far I have come up with the following exhausting permutation:

I am wondering if there is a better way to come up with a result which would suggest the 5 best team combinations based on the skillIndex. Do you guys have any idea what is an efficient way of solving this?

My end goal is to have two teams where one player can only be in one team. And the teams have a skillindex which is as close to each other as they can be.

My approach for now has been to find all possible combinations of the array, split this array in half so I have two teams. Then calculate the skillindex of both arrays and compare the difference between them. If the difference is <= 5 then print the generated team.

So one hard requirement is that with the same number of players teams consist of different players therefore I need multiple options.

const permutate = () => {
    const presentPlayers = [
        { name: 'a', skillIndex: 100 },
        { name: 'b', skillIndex: 100 },
        { name: 'c', skillIndex: 90 },
        { name: 'd', skillIndex: 25 },
        { name: 'e', skillIndex: 60 },
        { name: 'f', skillIndex: 80 },
        { name: 'g', skillIndex: 70 },
        { name: 'h', skillIndex: 60 },
        { name: 'i', skillIndex: 50 },
        { name: 'j', skillIndex: 50 },
    ];

    const getDifference = (a, b) => {
        return Math.abs(a - b);
    };

    function permutation(array) {
        function p(array, temp) {
            let i;
            let x;
            if (!array.length) {
                let team1Index = 0;
                let team2Index = 0;
                const half = temp.length / 2;
                const team1 = temp.splice(0, half);
                const team2 = temp.splice(-half);
                team1.forEach((player) => {
                    team1Index += parseFloat(player.skillIndex, 10);
                });
                team2.forEach((player) => {
                    team2Index += parseFloat(player.skillIndex, 10);
                });
                const difference = getDifference(team1Index, team2Index);
                if (difference === 5) {
                    console.log({ team1, team2 });
                    debugger;
                }
                result.push(temp);
            }
            for (i = 0; i < array.length; i++) {
                x = array.splice(i, 1)[0];
                p(array, temp.concat(x));
                array.splice(i, 0, x);
            }
        }

        const result = [];
        p(array, []);
        return result;
    }

    console.log(permutation(presentPlayers));
};

So for now I came up with this solution based mainly on the tips of you guys. I run this code 252 times:

            for (let i = 0; i < presentPlayers.length; i++) {
                const player = presentPlayers[i];
                players.push(player);
            }
            for (let i = players.length - 1; i > 0; i--) {
                const j = Math.floor(Math.random() * i);
                const temp = players[i];
                players[i] = players[j];
                players[j] = temp;
            }
            let team1Index = 0;
            let team2Index = 0;
            const half = players.length / 2;
            const team1 = players.splice(0, half);
            const team2 = players.splice(-half);
            team1.forEach((player) => {
                team1Index += parseFloat(player.skillIndex, 10);
            });
            team2.forEach((player) => {
                team2Index += parseFloat(player.skillIndex, 10);
            });
            const difference = getDifference(team1Index, team2Index);
            const sortedTeam1 = team1.sort((a, b) => {
                return b.skillIndex - a.skillIndex;
            });
            const sortedTeam2 = team2.sort((a, b) => {
                return b.skillIndex - a.skillIndex;
            });
            if (difference < 10) {
                proposedTeams.push({
                    sortedTeam1,
                    sortedTeam2,
                    difference,
                    team1Index,
                    team2Index,
                    goalSkill,
                });
            }

Answer 1

First, for your example you have, there are only 252 (10 choose 5) possible results. So trying all of them (brute force) is easily done.

In a more general matter, you can run a recursion method where at each level you assign a person to a team and check what can be done for the assigning of the next person. Keep in a global variable the best (closest) value you get to sumOfAllSkillIndex/2 and who was in what team.

Answer 2

Here is one approach. It does not try to be particularly efficient, because choosing five teams out of ten is a small problem. (10 choose 5 is only 252, and that already double-counts the splits into teams.) We can do this quickly enough not to matter for many practical purposes.

We should note that the data has 11 different splits into teams only five points apart, so you might want to test with data more varied, if that's realistic.

Here is an implementation:

// utility functions
const sum = (ns) => ns.reduce((a, b) => a + b, 0)

const combinations = (xs, n) => 
  xs .flatMap ((x, i) => 
    n == 1
      ? [[x]]
      : combinations (xs .slice (i + 1), n - 1) 
          .map (combo => [x, ...combo])
  )

const complement = (xs, ys) => xs .filter (x => !ys .includes (x))

const splits = (fn, xs) => 
  combinations (xs, Math.ceil(xs.length / 2))
    .map (c => [c, complement (xs, c)])
    .reduce (
      ({all, uniq}, [a, b], _, __, ka = fn(a), kb = fn(b)) =>
        uniq.has(ka) || uniq.has(kb) 
          ? {all, uniq} 
          : {all: all.concat([[a, b]]), uniq: uniq.add(ka).add(kb)},
      {all: [], uniq: new Set()}
    ).all


// helper function
const skillTotal = (players) =>
  sum (players .map (p => p. skillIndex))


// main function
const nClosestSplits = (n, players) => 
  splits (xs => xs.map(x => x.name).join('~'), players) .map (([a, b]) => ({
    teamA: a,
    teamB: b,
    scoreDiff: Math.abs(skillTotal(a) - skillTotal(b))
  }))
    .sort (({scoreDiff: a}, {scoreDiff: b}) => a - b)
    .slice (0, n)


// sample data
const presentPlayers = [{name: 'a', skillIndex: 100}, {name: 'b', skillIndex: 100}, {name: 'c', skillIndex: 90}, {name: 'd', skillIndex: 25}, {name: 'e', skillIndex: 60}, {name: 'f', skillIndex: 80}, {name: 'g', skillIndex: 70}, {name: 'h', skillIndex: 60}, {name: 'i', skillIndex: 50}, {name: 'j', skillIndex: 50}]


// demo
const display = (splits) =>
  console .log (splits.map(({teamA, teamB, scoreDiff}) => `[${
    teamA .map(a => `${a.name}`).join(', ')}] (total ${skillTotal(teamA)}) vs  [${
    teamB .map(b => `${b.name}`).join(', ')}] (total ${skillTotal(teamB)}),  diff = ${
    scoreDiff
  }`).join('\n'))

display (nClosestSplits (5, presentPlayers))

We start with some utility functions, ones that you might use across many parts of one project or across projects. I would probably place them in a personal utility library:

• sum simply adds together the numbers in a list

• combinations finds all subsets of n elements from a list of items. For example:

  combinations(['a', 'b', 'c', 'd'], 2) //=>
  // [["a", "b"], ["a", "c"], ["a", "d"], ["b", "c"], ["b", "d"], ["c", "d"]]
  

• complement find all the elements of one array not found in another.

  complement(['a', 'b', 'c', 'd', 'e'], ['a', 'd']) //=> ['b', 'c', 'e']
  

• splits uses combinations and complements to find all equal-sized partitions of a list of elements. It requires a helper function to turn our arrays into a single key to test on. We can't easily test the elements themselves, since we have to store them in a Set, which uses reference equality rather than value equality. So we might, for instance do this:

  splits ((xs) => xs.join('~'), ['a', 'b', 'c', 'd']) //=>
  // [
  //   [["a", "b"], ["c", "d"]], 
  //   [["a", "c"], ["b", "d"]], 
  //   [["a", "d"], ["b", "c"]]
  // ]
  

Then we have a single helper function (which I distinguish from utility functions because they are useful only in this problem, helping us factor into meaningful parts and/or reduce repetition in our main code):

• skillTotal just totals the skillIndex property for every player in an array.

We use these to build our main function nClosestSplits. This function takes n, the number of top values to choose, and a list of players. If finds all splits into teams, turns them into useful output objects with two teams and a score differential value, then sorts them by this differential, and chooses the top n values.

That sort/slice combination is less efficient than other methods of finding the top n values of an array. But it is easy to implement and is probably good enough if you are only looking at choosing five of ten players and hence have only 126 splits to compare. If you wanted to split 30 into 15, then you'd have 7.5 million to sort, and we might have to look for a more efficient implementation. They're not hard to find, but that will take us further afield.

Update

Following a suggestion in the comments, I added a shuffle function to help randomize among the (possibly many) top answers. Any decent shuffle function should do. I used this:

const shuffle = (_xs) => {
  const xs = [... _xs]
  for (let i = xs .length; i --> 0; ) {
    const j = Math .floor (Math .random () * i)
    xs [i] = [xs [j], xs [j] = xs [i]] [0] // or any swap method
  }
  return xs
}

with this change to the main function:

const nClosestSplits = (n, players, swap) => 
  shuffle(
    splits (xs => xs.map(x => x.name).join('~'), players) .map (([a, b]) => ({
      teamA: a,
      teamB: b,
      scoreDiff: Math.abs(skillTotal(a) - skillTotal(b))
    }))
  )
   .sort (({scoreDiff: a}, {scoreDiff: b}) => a - b)
   .slice (0, n)

which yields more randomized results such as

[a, b, d, g, i] (total 345)  vs  [c, e, f, h, j] (total 340),  diff = 5
[a, c, d, f, i] (total 345)  vs  [b, e, g, h, j] (total 340),  diff = 5
[a, b, d, e, h] (total 345)  vs  [c, f, g, i, j] (total 340),  diff = 5
[a, e, g, h, i] (total 340)  vs  [b, c, d, f, j] (total 345),  diff = 5
[a, c, d, g, h] (total 345)  vs  [b, e, f, i, j] (total 340),  diff = 5

It would be trivial to update to randomly choose the order of the two teams so that a is not always in the first team.

Answer 3

You could take all combinationbs for only the half, because the rest of the unuused indices are the rest of the other selection.

0 1 2 3 4 5 6 7 8 9  indices
0 1   3 4     7      one half selected
    2     5 6   8 9  other half is the rest without the first selected

This approach takes an index , sum and selected indices as well as a wanted target and a bias to select only result who have sums with a small bias of the target sum.

It feature as well a short circuit if the length of the selection is longer or the sum is greater than wanted target.

If the result is not wanted with sum or without indices, it could be adapted to the wanted result. Actually iit is easier to show only sum and indices.

const
    getCombinations = (data, key, size, target, bias = Number.MAX_VALUE) => {
        const
            iter = (index = 0, sum = 0, right = []) => {
                if (right.length === size) {
                    if (Math.abs(target - sum) <= bias) result.push([sum, ...right]);
                    return;
                }
                if (index === data.length || sum > target + bias) return;

                iter(index + 1, sum + data[index][key], [...right, index]);
                iter(index + 1, sum, right);
            },
            result = [];

        iter();
        return result;
    },
    presentPlayers = [{ name: 'a', skillIndex: 100 }, { name: 'b', skillIndex: 100 }, { name: 'c', skillIndex: 90 }, { name: 'd', skillIndex: 25 }, { name: 'e', skillIndex: 60 }, { name: 'f', skillIndex: 80 }, { name: 'g', skillIndex: 70 }, { name: 'h', skillIndex: 60 }, { name: 'i', skillIndex: 50 }, { name: 'j', skillIndex: 50 }],
    target = presentPlayers.reduce((s, { skillIndex }) => s + skillIndex, 0) / 2,
    result = getCombinations(
        presentPlayers,
        'skillIndex',
        presentPlayers.length >> 1,
        target,
        5
    );

console.log('sum', '|', 'indices');
result.forEach(([sum, ...indices]) => console.log(sum, '|', indices.join(' ')));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 4

This may not be the absolute most balanced, but it'll be damn close every time, and very fast.

const presentPlayers = [
    { name: 'a', skillIndex: 100 },
    { name: 'b', skillIndex: 100 },
    { name: 'c', skillIndex: 90 },
    { name: 'd', skillIndex: 25 },
    { name: 'e', skillIndex: 60 },
    { name: 'f', skillIndex: 80 },
    { name: 'g', skillIndex: 70 },
    { name: 'h', skillIndex: 60 },
    { name: 'i', skillIndex: 45 },
    { name: 'j', skillIndex: 50 },
    { name: 'k', skillIndex: 100 },
    { name: 'l', skillIndex: 60 },
    { name: 'm', skillIndex: 75 },
    { name: 'n', skillIndex: 35 },
];


function FastAssignment(players) {

    const sorted = players.sort((a, b) => b.skillIndex - a.skillIndex);

    // init with first two highest skilled players
    let team_a = [sorted.shift()];
    let team_b = [sorted.shift()];

    // start tracking total skill for each team
    let score_a = team_a[0].skillIndex;
    let score_b = team_b[0].skillIndex;

    // check them 2 at a time
    // assumes array is always divisible by two
    while (sorted.length > 0) {
        let a = sorted.shift()
        let b = sorted.shift()

        let high, low;

        // figure out which is higher / lower
        if (a.skillIndex >= b.skillIndex) {
            high = a;
            low = b;
        } else {
            high = b;
            low = a;
        }

        // check total score for team
        // assign lower skilled player to higher scored team
        if (score_a >= score_b) {
            team_a.push(low)
            team_b.push(high)
            score_a += low.skillIndex
            score_b += high.skillIndex
        } else {
            team_a.push(high)
            team_b.push(low)
            score_a += high.skillIndex
            score_b += low.skillIndex
        }
    }

    return [team_a, team_b]
}

function PrintTeamPair(pair){
    const [team_a, team_b] = pair;
    console.log(team_a)
    console.log('A total:', team_a.reduce((a, i) => a + i.skillIndex, 0))
    console.log(team_b)
    console.log('B total:', team_b.reduce((a, i) => a + i.skillIndex, 0))
    console.log('>>>>>>>>>>>>>>')
}

function ShuffleTeamPair(pair){
    const [team_a, team_b] = pair;
    let selections = [];
    for (let i = 0; i < team_a.length; i++) {
        let a = [...team_a.slice(0, i), team_b[i], ...team_a.slice(i+1)];
        let b = [...team_b.slice(0, i), team_a[i], ...team_b.slice(i+1)];
        selections.push([a, b])
    }
    return selections;
}

const two_teams = FastAssignment(presentPlayers)
const shuffled = ShuffleTeamPair(two_teams)

PrintTeamPair(two_teams)

for(let pair of shuffled){
    PrintTeamPair(pair)
}

Output:

[
  { name: 'a', skillIndex: 100 },
  { name: 'c', skillIndex: 90 },
  { name: 'f', skillIndex: 80 },
  { name: 'g', skillIndex: 70 },
  { name: 'l', skillIndex: 60 },
  { name: 'i', skillIndex: 45 },
  { name: 'd', skillIndex: 25 }
]
A total: 470
[
  { name: 'b', skillIndex: 100 },
  { name: 'k', skillIndex: 100 },
  { name: 'm', skillIndex: 75 },
  { name: 'e', skillIndex: 60 },
  { name: 'h', skillIndex: 60 },
  { name: 'j', skillIndex: 50 },
  { name: 'n', skillIndex: 35 }
]
B total: 480
>>>>>>>>>>>>>>
[
  { name: 'b', skillIndex: 100 },
  { name: 'c', skillIndex: 90 },
  { name: 'f', skillIndex: 80 },
  { name: 'g', skillIndex: 70 },
  { name: 'l', skillIndex: 60 },
  { name: 'i', skillIndex: 45 },
  { name: 'd', skillIndex: 25 }
]
A total: 470
[
  { name: 'a', skillIndex: 100 },
  { name: 'k', skillIndex: 100 },
  { name: 'm', skillIndex: 75 },
  { name: 'e', skillIndex: 60 },
  { name: 'h', skillIndex: 60 },
  { name: 'j', skillIndex: 50 },
  { name: 'n', skillIndex: 35 }
]
B total: 480
>>>>>>>>>>>>>>
[
  { name: 'a', skillIndex: 100 },
  { name: 'k', skillIndex: 100 },
  { name: 'f', skillIndex: 80 },
  { name: 'g', skillIndex: 70 },
  { name: 'l', skillIndex: 60 },
  { name: 'i', skillIndex: 45 },
  { name: 'd', skillIndex: 25 }
]
A total: 480
[
  { name: 'b', skillIndex: 100 },
  { name: 'c', skillIndex: 90 },
  { name: 'm', skillIndex: 75 },
  { name: 'e', skillIndex: 60 },
  { name: 'h', skillIndex: 60 },
  { name: 'j', skillIndex: 50 },
  { name: 'n', skillIndex: 35 }
]
B total: 470
>>>>>>>>>>>>>>
[
  { name: 'a', skillIndex: 100 },
  { name: 'c', skillIndex: 90 },
  { name: 'm', skillIndex: 75 },
  { name: 'g', skillIndex: 70 },
  { name: 'l', skillIndex: 60 },
  { name: 'i', skillIndex: 45 },
  { name: 'd', skillIndex: 25 }
]
A total: 465
[
  { name: 'b', skillIndex: 100 },
  { name: 'k', skillIndex: 100 },
  { name: 'f', skillIndex: 80 },
  { name: 'e', skillIndex: 60 },
  { name: 'h', skillIndex: 60 },
  { name: 'j', skillIndex: 50 },
  { name: 'n', skillIndex: 35 }
]
B total: 485
>>>>>>>>>>>>>>
[
  { name: 'a', skillIndex: 100 },
  { name: 'c', skillIndex: 90 },
  { name: 'f', skillIndex: 80 },
  { name: 'e', skillIndex: 60 },
  { name: 'l', skillIndex: 60 },
  { name: 'i', skillIndex: 45 },
  { name: 'd', skillIndex: 25 }
]
A total: 460
[
  { name: 'b', skillIndex: 100 },
  { name: 'k', skillIndex: 100 },
  { name: 'm', skillIndex: 75 },
  { name: 'g', skillIndex: 70 },
  { name: 'h', skillIndex: 60 },
  { name: 'j', skillIndex: 50 },
  { name: 'n', skillIndex: 35 }
]
B total: 490
>>>>>>>>>>>>>>
[
  { name: 'a', skillIndex: 100 },
  { name: 'c', skillIndex: 90 },
  { name: 'f', skillIndex: 80 },
  { name: 'g', skillIndex: 70 },
  { name: 'h', skillIndex: 60 },
  { name: 'i', skillIndex: 45 },
  { name: 'd', skillIndex: 25 }
]
A total: 470
[
  { name: 'b', skillIndex: 100 },
  { name: 'k', skillIndex: 100 },
  { name: 'm', skillIndex: 75 },
  { name: 'e', skillIndex: 60 },
  { name: 'l', skillIndex: 60 },
  { name: 'j', skillIndex: 50 },
  { name: 'n', skillIndex: 35 }
]
B total: 480
>>>>>>>>>>>>>>
[
  { name: 'a', skillIndex: 100 },
  { name: 'c', skillIndex: 90 },
  { name: 'f', skillIndex: 80 },
  { name: 'g', skillIndex: 70 },
  { name: 'l', skillIndex: 60 },
  { name: 'j', skillIndex: 50 },
  { name: 'd', skillIndex: 25 }
]
A total: 475
[
  { name: 'b', skillIndex: 100 },
  { name: 'k', skillIndex: 100 },
  { name: 'm', skillIndex: 75 },
  { name: 'e', skillIndex: 60 },
  { name: 'h', skillIndex: 60 },
  { name: 'i', skillIndex: 45 },
  { name: 'n', skillIndex: 35 }
]
B total: 475
>>>>>>>>>>>>>>
[
  { name: 'a', skillIndex: 100 },
  { name: 'c', skillIndex: 90 },
  { name: 'f', skillIndex: 80 },
  { name: 'g', skillIndex: 70 },
  { name: 'l', skillIndex: 60 },
  { name: 'i', skillIndex: 45 },
  { name: 'n', skillIndex: 35 }
]
A total: 480
[
  { name: 'b', skillIndex: 100 },
  { name: 'k', skillIndex: 100 },
  { name: 'm', skillIndex: 75 },
  { name: 'e', skillIndex: 60 },
  { name: 'h', skillIndex: 60 },
  { name: 'j', skillIndex: 50 },
  { name: 'd', skillIndex: 25 }
]
B total: 470
>>>>>>>>>>>>>>