さらに強力なチームを生成するための最善のアルゴリズム

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： プレーヤー2、スキル50; プレイヤー1、スキル25

チームが4 + 1でプレイヤー3 + 2であれば、より公平になります。 もっと公平なアルゴリズムについて知っていますか？手伝ってくれてありがとう！

Answer 1

YouTube - The Fairest Sharing Sequence Ever - Standup Mathsで見られるように、Thue-Morse Sequenceは、おそらく最初のターンの利点を最小限に抑えるための最良の賭けです。

ウィキペディア：数学の

、Thue-Morseの配列、またはProuhet-Thue-Morseのシーケンスは、0から始まる順次付加することによって得られるバイナリ列（0と1の無限配列）でありますこれまでに得られたシーケンスのブール値の補数。この手順の最初の数ステップでは、Thue-Morseシーケンスの接頭辞である0、01、0110、01101001、0110100110010110などの文字列が生成されます。スキルに基づいてソートされたリストで、このターンの順番を使用して

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

：SO著作権承認されたバージョンを取得するには、Pythonの答えからの移植...

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

レベルはより公平なチームを与えるべきであり、+ -1のメンバーの中にいるというあなたの制約を満たす。

online encyclopedia of integer sequences (A010060)に対して確認された最初の105桁を生成します。

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

}