I'm trying to write a method that groups objects into the minimum amount of sublists without mixing types (int field on object) or the sum of their values exceeding a defined maximum value. It should look something like this:
List<List<Foo>> group(List<Foo> values, int maximumValue);
This is my pojo class (actual sample code at the bottom includes constructor and accessors):
public class Foo {
int type;
int value;
}
Here is a sample input and the expected output:
Input:
maximumValue=50
Foo [type=1, value=27]
Foo [type=1, value=24]
Foo [type=1, value=18]
Foo [type=1, value=13]
Foo [type=1, value=10]
Foo [type=1, value=7]
Foo [type=2, value=39]
Foo [type=2, value=34]
Foo [type=2, value=15]
Foo [type=2, value=5]
Expected output:
Foo [type=1, value=27]
Foo [type=1, value=13]
Foo [type=1, value=10]
sum=50
Foo [type=1, value=24]
Foo [type=1, value=18]
Foo [type=1, value=7]
sum=49
Foo [type=2, value=39]
Foo [type=2, value=5]
sum=44
Foo [type=2, value=34]
Foo [type=2, value=15]
sum=49
When trying to implement my grouping method I found this answer which already seemed very close to what I need: Rearrange int array, sort into groups with a sum maximum in Java
My current implementation is essentially the same, just adjusted for using an object instead of directly grouping integers plus separation by type:
public List<List<Foo>> group(List<Foo> values, int maximumValue) {
List<List<Foo>> sublists = new ArrayList<>();
// at first group by type
Map<?, List<Foo>> typeGroups = values.stream().collect(Collectors.groupingBy(Foo::getType));
for (List<Foo> input : typeGroups.values()) {
input.sort(Comparator.comparingInt(Foo::getValue));
List<List<Foo>> result = new ArrayList<>();
result.add(new ArrayList<Foo>());
// Initialize the sums of the groups, to increase performance (I guess).
ArrayList<Integer> sums = new ArrayList<>();
sums.add(0);
while (!input.isEmpty()) {
Foo foo = input.get(0);
int value = foo.getValue();
boolean match = false;
// Search the next groups and check if our current
// number ('n') fits.
for (int i = 0; i < sums.size(); i++) {
if (sums.get(i) + value <= maximumValue) {
// If it fits, then add the number to the group.
sums.set(i, sums.get(i) + value);
result.get(i).add(foo);
match = true;
break;
}
}
// If 'n' doesn't fit in any group, create a new one.
if (!match) {
List<Foo> newGroup = new ArrayList<>();
newGroup.add(foo);
result.add(newGroup);
sums.add(value);
}
// Remove our number.
input.remove(0);
}
sublists.addAll(result);
}
return sublists;
}
Calling this function with the sample input from earlier gives me the following output:
Foo [type=1, value=7]
Foo [type=1, value=10]
Foo [type=1, value=13]
Foo [type=1, value=18]
sum=48
Foo [type=1, value=24]
sum=24
Foo [type=1, value=27]
sum=27
Foo [type=2, value=5]
Foo [type=2, value=15]
sum=20
Foo [type=2, value=34]
sum=34
Foo [type=2, value=39]
sum=39
Those are 6 groups but it is possible (as seen in the example earlier) to group the input into only 4 groups. I tried reversing the sort order from ascending to descending which improves the result to 5 groups but doesn't fix the underlying issue whatsoever and still isn't even the smallest possible number of groups.
Here is small self-contained class I wrote for testing & adjusting:
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class ObjectGrouping {
public static void main(String[] args) {
int maximumValue = 50;
List<Foo> values = new ArrayList<>();
values.add(new Foo(1, 27));
values.add(new Foo(1, 24));
values.add(new Foo(1, 18));
values.add(new Foo(1, 13));
values.add(new Foo(1, 10));
values.add(new Foo(1, 7));
// ideal groups: [27, 13, 10], [24, 18, 7]
values.add(new Foo(2, 39));
values.add(new Foo(2, 34));
values.add(new Foo(2, 15));
values.add(new Foo(2, 5));
// ideal groups: [39, 15], [34, 5] (which way exactly doesn't matter as long as it's 2 groups)
System.out.println("input:");
values.forEach(System.out::println);
System.out.println();
System.out.println();
List<List<Foo>> result = group(values, maximumValue);
System.out.println("result:");
for (List<Foo> list : result) {
list.forEach(System.out::println);
// check if all objects are of the same group
assert list.stream().map(Foo::getType).distinct().count() == 1;
// check if sum of values does not exceed maximum value
int sum = list.stream().mapToInt(Foo::getValue).sum();
System.out.println("sum=" + sum);
assert sum <= maximumValue;
}
}
public static List<List<Foo>> group(List<Foo> values, int maximumValue) {
List<List<Foo>> sublists = new ArrayList<>();
// at first group by type
Map<?, List<Foo>> typeGroups = values.stream().collect(Collectors.groupingBy(Foo::getType));
for (List<Foo> input : typeGroups.values()) {
input.sort(Comparator.comparingInt(Foo::getValue));
List<List<Foo>> result = new ArrayList<>();
result.add(new ArrayList<Foo>());
// Initialize the sums of the groups, to increase performance (I guess).
ArrayList<Integer> sums = new ArrayList<>();
sums.add(0);
while (!input.isEmpty()) {
Foo foo = input.get(0);
int value = foo.getValue();
boolean match = false;
// Search the next groups and check if our current
// number ('n') fits.
for (int i = 0; i < sums.size(); i++) {
if (sums.get(i) + value <= maximumValue) {
// If it fits, then add the number to the group.
sums.set(i, sums.get(i) + value);
result.get(i).add(foo);
match = true;
break;
}
}
// If 'n' doesn't fit in any group, create a new one.
if (!match) {
List<Foo> newGroup = new ArrayList<>();
newGroup.add(foo);
result.add(newGroup);
sums.add(value);
}
// Remove our number.
input.remove(0);
}
sublists.addAll(result);
}
return sublists;
}
public static class Foo {
private int type;
private int value;
public Foo(int type, int value) {
this.type = type;
this.value = value;
}
public int getType() {
return type;
}
public int getValue() {
return value;
}
public void setType(int type) {
this.type = type;
}
public void setValue(int value) {
this.value = value;
}
@Override
public String toString() {
return "Foo [type=" + type + ", value=" + value + "]";
}
}
}
I would be fine with either fixing the existing algorithm or using a completely new one, I was thinking that it might be possible to use the Streams API and implement a custom Collector but not sure. Any help is greatly appreciated, thanks.
