产生更强团队的最佳算法

Question

我得到了一份0-100人的球员名单和一份拥有自己所有成员名单的球队名单。

现在我想把球员放在团队中，这样团队的大小基本相同（-1差异是可以的），并且技能的总和应该尽可能接近。

我目前的解决方案是一个简单的投票算法（团队在圆圈中投票球员，然后选出下一个最佳球员）：

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

问题是，给出的不是最均匀的团队，控制台输出是：

球队1：球员4，技能75;玩家 3， 技能 50

第二队：球员2，技能50；球员1，技能25

但如果球队是4 1和球员3 2，那就更公平了。你对更公平的算法有什么想法吗？感谢您的帮助！

Answer 1

如YouTube所见——有史以来最公平的共享序列——苏莫尔斯序列站立数学可能是您最大限度地减少第一回合优势的最佳选择。

维基百科：

在数学中，Thue–Morse序列或Prouhet–Thue–Morse序列是一个二进制序列（0和1的无限序列），它是从0开始，然后依次附加到目前为止获得的序列的布尔补码。此过程的前几个步骤生成字符串0，然后是01、0110、01101001、0110100110010110，依此类推，它们是Thue–Morse序列的前缀。。。

计算机科学入门 - 普林斯顿

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

从Python答案移植，以获得版权认可的版本:

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

使用这个转弯顺序，根据技能水平排序的列表应该会给更公平的团队，并满足你在-1成员内的限制。

通过生成前 105 位数字，根据整数序列的在线百科全书 （A010060） 进行验证。

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

}