Geek Answers Handbook

Java how to split treemap into two equal maps based on values

Ok, I have this treemap that contains playerID and mid-level players. I want to split it into two other cards, so each team has an even number of players, and the player’s total score is about the same (deviation is about +/- 2)

private TreeMap<Integer, Double> teamScoreMap = new TreeMap<>(); private TreeMap<Integer, Double> team1 = new TreeMap<>(); private TreeMap<Integer, Double> team2 = new TreeMap<>(); public void createTeam() { teamScoreMap.put(001, 5.0); teamScoreMap.put(002, 8.4); teamScoreMap.put(003, 2.1); teamScoreMap.put(004, 6.5); teamScoreMap.put(005, 4.5); teamScoreMap.put(006, 3.2); teamScoreMap.put(007, 9.8); teamScoreMap.put(008, 7.6); }
+5
source share
3 answers

try it

 TreeMap<Integer,Double> teamScoreMap = new TreeMap<Integer, Integer>(bigMap); int size = teamScoreMap.size(); SortedMap<Integer, Double> team1 = teamScoreMap .subMap(0, size/2); SortedMap<Integer, Double> team2 = teamScoreMap .subMap((size/2)+1,size);

There is no reason to really throw in TreeMap, because it does not provide any additional features over what SortedMap does.

+1
source

There is logic, you just need to finish the code to add each command to each card.

Make all possible teams, compare their average with the previous best average. If the difference is lower than the previous one, replace them.

In the end, you will get the best difference between both.

Output example

 {false=[1=5.0, 4=6.5, 5=4.5, 8=7.6], true=[2=8.4, 3=2.1, 6=3.2, 7=9.8]} // false = 23.6 in total true = 23.5 in total // As you see, the difference between both is the minimum possible (0.1) 
 public class Test { private Map<Integer, Double> tsm = new TreeMap<>(); private Map<Integer, Double> team1 = new TreeMap<>(); private Map<Integer, Double> team2 = new TreeMap<>(); public void splitTeams() { double average = tsm.values() .stream() .mapToDouble(x->x) .average() .getAsDouble(); int[] bestTeam = new int[4]; double bestAverage = 10; double tmp; for (int i = 1 ; i <= 8 ; i++) { for (int j = 1 ; j <= 8 ; j++) { for (int k = 1 ; k <= 8 ; k++) { for (int l = 1 ; l <= 8 ; l++) { if (Stream.of(i, j, k, l).distinct().count() == 4) { tmp = Stream.of(tsm.get(i), tsm.get(j), tsm.get(k), tsm.get(l)) .mapToDouble(x -> x) .average() .getAsDouble(); if (Math.abs(average - tmp) < bestAverage) { bestTeam[0] = i; bestTeam[1] = j; bestTeam[2] = k; bestTeam[3] = l; bestAverage = Math.abs(average - tmp); } } } } } } List<Integer> team1 = Arrays.stream(bestTeam).boxed().collect(Collectors.toList()); Map<Boolean, List<Entry<Integer, Double>>> both = tsm.entrySet() .stream() .collect(Collectors.partitioningBy(e -> team1.contains(e.getKey()))); System.out.println(both); } public void createTeam() { tsm.put(1, 5.0); tsm.put(2, 8.4); tsm.put(3, 2.1); tsm.put(4, 6.5); tsm.put(5, 4.5); tsm.put(6, 3.2); tsm.put(7, 9.8); tsm.put(8, 7.6); } public static void main(String[] args) { Test t = new Test(); t.createTeam(); t.splitTeams(); System.out.println(); } }
+1
source

Yassin Hajaj's answer shows one way to calculate the optimal result for this particular case. More generally, what you are trying to solve is a special instance of the problem of summing up a subset , and there are related questions - for example. divide the array into two sets with the minimum difference .

In principle, there is no effective way to find the optimal solution.

The brute force method for calculating the optimal solution is to calculate all possible options from half the elements, calculate their sum and find the sum that has the smallest deviation from the required amount.

However, in many cases the optimal solution is not interesting. but only in a “good” solution. This can be achieved using a greedy approach: first, sort the grades in descending order. Then go to the list of team members and assign each of them to the team that currently has a lower score.

Both approaches are implemented here as an example:

 import java.math.BigInteger; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.Iterator; import java.util.LinkedHashSet; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.NoSuchElementException; import java.util.Set; import java.util.TreeMap; public class MapSplit { public static void main(String[] args) { TreeMap<Integer, Double> teamScoreMap = new TreeMap<Integer, Double>(); teamScoreMap.put(1, 5.0); teamScoreMap.put(2, 8.4); teamScoreMap.put(3, 2.1); teamScoreMap.put(4, 6.5); teamScoreMap.put(5, 4.5); teamScoreMap.put(6, 3.2); teamScoreMap.put(7, 9.8); teamScoreMap.put(8, 7.6); solveOptimal(teamScoreMap); solveGreedy(teamScoreMap); } private static void solveOptimal(Map<Integer, Double> teamScoreMap) { List<Entry<Integer, Double>> entries = new ArrayList<Entry<Integer, Double>>( teamScoreMap.entrySet()); double totalSum = computeSum(entries); ChoiceIterable<Entry<Integer, Double>> ci = new ChoiceIterable<Entry<Integer, Double>>( teamScoreMap.size() / 2, entries); List<Entry<Integer, Double>> bestTeam = null; double minError = Double.POSITIVE_INFINITY; for (List<Entry<Integer, Double>> team : ci) { double teamSum = computeSum(team); double error = Math.abs(teamSum - totalSum * 0.5); if (error < minError) { bestTeam = team; minError = error; } } Set<Entry<Integer, Double>> teamA = new LinkedHashSet<Entry<Integer, Double>>(bestTeam); Set<Entry<Integer, Double>> teamB = new LinkedHashSet<Entry<Integer, Double>>( teamScoreMap.entrySet()); teamB.removeAll(teamA); System.out.println("Optimal result:"); printResult(teamA, teamB); } private static void solveGreedy(Map<Integer, Double> teamScoreMap) { List<Entry<Integer, Double>> entries = new ArrayList<Entry<Integer, Double>>( teamScoreMap.entrySet()); Collections.sort(entries, (e0, e1) -> Double.compare(e1.getValue(), e0.getValue())); Set<Entry<Integer, Double>> teamA = new LinkedHashSet<Entry<Integer, Double>>(); double sumA = 0; Set<Entry<Integer, Double>> teamB = new LinkedHashSet<Entry<Integer, Double>>(); double sumB = 0; for (Entry<Integer, Double> entry : entries) { if (sumA < sumB) { teamA.add(entry); sumA += entry.getValue(); } else { teamB.add(entry); sumB += entry.getValue(); } } System.out.println("Greedy result:"); printResult(teamA, teamB); } private static void printResult( Collection<Entry<Integer, Double>> teamA, Collection<Entry<Integer, Double>> teamB) { System.out.println("Team A:"); for (Entry<Integer, Double> entry : teamA) { System.out.println(" " + entry); } System.out.println("Sum: " + computeSum(teamA)); System.out.println("Team B:"); for (Entry<Integer, Double> entry : teamB) { System.out.println(" " + entry); } System.out.println("Sum: " + computeSum(teamB)); } private static double computeSum( Collection<Entry<Integer, Double>> entries) { return entries.stream().map( e -> e.getValue()).reduce(0.0, (a,b) -> a+b); } } // From https://github.com/javagl/Combinatorics/blob/master/src/main/ // java/de/javagl/utils/math/combinatorics/CombinationIterable.java class ChoiceIterable<T> implements Iterable<List<T>> { private final List<T> input; private final int sampleSize; private final long numElements; public ChoiceIterable(int sampleSize, List<T> input) { this.sampleSize = sampleSize; this.input = input; BigInteger nf = factorial(input.size()); BigInteger kf = factorial(sampleSize); BigInteger nmkf = factorial(input.size() - sampleSize); BigInteger divisor = kf.multiply(nmkf); BigInteger result = nf.divide(divisor); numElements = result.longValue(); } public static BigInteger factorial(int n) { BigInteger f = BigInteger.ONE; for (int i = 2; i <= n; i++) { f = f.multiply(BigInteger.valueOf(i)); } return f; } @Override public Iterator<List<T>> iterator() { return new Iterator<List<T>>() { private int current = 0; private final int chosen[] = new int[sampleSize]; // Initialization of first choice { for (int i = 0; i < sampleSize; i++) { chosen[i] = i; } } @Override public boolean hasNext() { return current < numElements; } @Override public List<T> next() { if (!hasNext()) { throw new NoSuchElementException("No more elements"); } List<T> result = new ArrayList<T>(sampleSize); for (int i = 0; i < sampleSize; i++) { result.add(input.get(chosen[i])); } current++; if (current < numElements) { increase(sampleSize - 1, input.size() - 1); } return result; } private void increase(int n, int max) { if (chosen[n] < max) { chosen[n]++; for (int i = n + 1; i < sampleSize; i++) { chosen[i] = chosen[i - 1] + 1; } } else { increase(n - 1, max - 1); } } @Override public void remove() { throw new UnsupportedOperationException( "May not remove elements from a choice"); } }; } }

(the class for calculating the selection is taken from here )

The output is as follows:

 Optimal result: Team A: 1=5.0 4=6.5 5=4.5 8=7.6 Sum: 23.6 Team B: 2=8.4 3=2.1 6=3.2 7=9.8 Sum: 23.5 Greedy result: Team A: 2=8.4 8=7.6 1=5.0 3=2.1 Sum: 23.1 Team B: 7=9.8 4=6.5 5=4.5 6=3.2 Sum: 24.0

showing that the greedy result is not optimal, but in this case it is pretty good.

0
source

More articles:


All Articles