The best algorithm for generating even strong teams
I have a list of players with a skill from 0 to 100 and a list of teams that have a list of all their members.
Now I want to put players into teams so that the teams basically get the same size (+ -1 order difference) and the skill sums should be as close as possible.
My current solution is a simple voting algorithm (teams run players in a circle, pick 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 it does not issue the clearest commands, the console output:
Team 1: Player 4, skill 75; Player 3, Skill 50
Team 2: Player 2, skill 50; Player 1, Skill 25
But it would be fairer if the teams were 4 + 1 and player 3 + 2. Do you have an idea for a fairer algorithm? Thanks for the help!
source to share
As seen on YouTube - Most Efficient Sequence in Seconds Ever Standing Math Thue-Morse Sequence is probably your best bet for minimizing benefits in the first place.
Wikipedia:
In mathematics, the Thue-Morse sequence, or the Prouet-Thue-Morse sequence, is a binary sequence (an infinite sequence of 0s and 1s) obtained by starting at 0 and sequentially adding the logical complement of the sequence thus obtained far away.The first few steps of this procedure yield strings 0 , then 01, 0110, 01101001, 0110100110010110, etc., which are prefixes to the Thue-Morse sequence ....
Introduction to 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 Python's answer to get the SO approved version:
public static int whoseTurn(int turnCount){
return Integer.bitCount(turnCount) % 2;
}
Using this pivot order, with a sorted list based on skill level, should give more honest commands and fit your + -1 member limit.
Checked on Online Encyclopedia of Integer Sequences (A010060) by generating 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;
}
}
source to share