Best algorithm to generate even strong teams

Question

I got a list of players with a skill from 0-100 and a list of teams which have all their own members list.

Now I want to put the players to the teams so that teams mostly got the same size (+-1 difference is ok) and the sums of the skills should be as close at possible.

My current solution is a simple voting algorithm (teams vote players in circle, an take the next best player):

public class Teamgenerator {
    public void calcTeams(){
        List<Team> teams = new ArrayList<>();
        teams.add(new Team("Team 1"));
        teams.add(new Team("Team 2"));

        List<Player> players = new ArrayList<>();
        players.add(new Player("Player 1",25));
        players.add(new Player("Player 2",50));
        players.add(new Player("Player 3",50));
        players.add(new Player("Player 4",75));

        int nextTeam = 0;
        while (players.size() > 0) {
            int bestPlayer = findBestPlayerIndex(players);
            teams.get(nextTeam).players.add(players.get(bestPlayer));
            players.remove(bestPlayer);

            if (nextTeam < teams.size() - 1) nextTeam++;
            else nextTeam = 0;
        }

        for(Team t:teams){
            System.out.println(t.getName()+":");
            for(Player p:t.players)
                System.out.println(p.getName()+", Skill "+p.getSkill());
        }
    }


    private int findBestPlayerIndex(List<Player> players) {
        //In my real programm i have to pick the skill of a more complex player object from a DB, 
        //depending on a specific competition,  which causes i really need this index finding
        int index = -1;
        int highestSkill=-1;
        for (int i = 0; i < players.size(); i++) {
            if (players.get(i).getSkill() > highestSkill) {
                highestSkill = players.get(i).getSkill();
                index = i;
            }
        }
        return index;
    }
}

public class Team {
    private String name;
    public ArrayList<Player> players=new ArrayList<>();

    public Team(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

public class Player {
    private String name;
    private int skill=50; //From 0-100

    public Player(String name, int skill) {
        this.name = name;
        this.skill = skill;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getSkill() {
        return skill;
    }

    public void setSkill(int skill) {
        this.skill = skill;
    }   
}

The problem is that gives not the most even teams, console output is:

Team 1: Player 4, Skill 75; Player 3, Skill 50

Team 2: Player 2, Skill 50; Player 1, Skill 25

But it would be more fair if the teams are 4+1 and player 3+2. You got any idea of a more fair algorithm? Thanks for help!

Answer 1

As seen on YouTube - The Fairest Sharing Sequence Ever - Standup Maths the Thue-Morse Sequence is probably your best bet for minimising first turn advantage.

Wikipedia:

In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence, is the binary sequence (an infinite sequence of 0s and 1s) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. The first few steps of this procedure yield the strings 0 then 01, 0110, 01101001, 0110100110010110, and so on, which are prefixes of the Thue–Morse sequence. ...

Intro Computer Science - Princeton

//Copyright © 2000–2016, Robert Sedgewick and Kevin Wayne. 
public class ThueMorse { 
   public static void main(String[] args) { 
        int n = Integer.parseInt(args[0]);
        String thue   = "0";
        String morse  = "1";

        for (int i = 1; i <= n; i++) {
            String t = thue;             // save away values
            String m = morse;
            thue  += m;
            morse += t;
        }
        System.out.println(thue);
    }
}

Porting from a Python answer, to get a SO copyright approved version:

public static int whoseTurn(int turnCount){
    return Integer.bitCount(turnCount) % 2;
}

Using this turn order, with a sorted list based on skill level should give fairer teams, and meet your constraint of being within +-1 member.

Verified against the online encyclopedia of integer sequences (A010060) by generating the first 105 digits.

import java.util.stream.IntStream;

public class NodeStack {

public static int whoseTurn(int turnCount){
    return Integer.bitCount(turnCount) % 2;
}

public static void main(String[] args) {
    System.out.print("OEIS: ");
    IntStream.range(0,105).map(NodeStack::whoseTurn).forEach(i->System.out.print(i+", "));
    String result = IntStream.range(0,105).map(NodeStack::whoseTurn).collect(StringBuilder::new,(sb,i)->sb.append(i), StringBuilder::append).toString();
    System.out.println();
    IntStream.range(1,105).forEach(
            (i)-> System.out.println(i+"# "+result.substring(0,i)+ " : " +diff(result.substring(0,i)))
    );
}

public static int diff(String s){
    int zero = 0;
    int one = 0;
    for (char c:s.toCharArray()){
        if (c=='0')zero++;
        if (c=='1')one++;
    }
    return zero-one;
}

}