'Group list of objects into smallest possible number of sublists without exceeding maximum sum
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.
Solution 1:[1]
Alright. So how I went about it, was to generate all possible combinations for each group. The algorithm was taken from this answer. I then applied the max value filter to it. After that, I created a sorted map with the difference between maximumValue
and the summed total of a list and only added it it the result, if none of the elements already existed in the result. It's probably not the sexiest solution, but it gets the expected results.
public class Test {
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));
List<List<Foo>> allResult = group(values, maximumValue);
for (List<Foo> list : allResult) {
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;
}
}
/**
* @param maximumValue
* @return
*
*/
private static List<List<Foo>> group(List<Foo> values, int maximumValue) {
List<List<Foo>> allResult = new ArrayList<>();
Map<?, List<Foo>> typeGroups = values.stream().collect(Collectors.groupingBy(Foo::getType));
for (List<Foo> input : typeGroups.values()) {
List<List<Foo>> collect = combinations(input.toArray(new Foo[] {}), maximumValue)
.collect(Collectors.toList());
// collect.forEach(e -> System.out.println(e));
Map<List<Foo>, Integer> diffMap = new HashMap<>();
for (List<Foo> data : collect) {
int sum = data.stream().mapToInt(e -> e.value).sum();
diffMap.put(data, maximumValue - sum);
}
allResult.addAll(sortByValueAndFilter(diffMap));
}
return allResult;
}
private static List<List<Foo>> sortByValueAndFilter(Map<List<Foo>, Integer> diffMap) {
List<Entry<List<Foo>, Integer>> list = new ArrayList<>(diffMap.entrySet());
list.sort(Entry.comparingByValue());
Map<List<Foo>, Integer> result = new LinkedHashMap<>();
for (Entry<List<Foo>, Integer> entry : list) {
result.put(entry.getKey(), entry.getValue());
}
List<List<Foo>> resultList = new ArrayList<>();
for (Entry<List<Foo>, Integer> entry2 : result.entrySet()) {
if (!checkResultContainsElement(resultList, entry2.getKey()))
resultList.add(entry2.getKey());
}
return resultList;
}
private static boolean checkResultContainsElement(List<List<Foo>> resultList, List<Foo> key) {
boolean res = false;
for (Foo integer : key) {
for (Foo i : resultList.stream().flatMap(e -> e.stream()).collect(Collectors.toList())) {
if (i.value == integer.value) {
res = true;
break;
}
}
if (res)
break;
}
return res;
}
/**
*
* Property of https://stackoverflow.com/a/37836750/7109162
*
* @param arr
* @param maximumValue
* @return
*/
public static Stream<List<Foo>> combinations(Foo[] arr, int maximumValue) {
final long N = (long) Math.pow(2, arr.length);
return StreamSupport.stream(new AbstractSpliterator<List<Foo>>(N, Spliterator.SIZED) {
long i = 1;
@Override
public boolean tryAdvance(Consumer<? super List<Foo>> action) {
if (i < N) {
List<Foo> out = new ArrayList<Foo>(Long.bitCount(i));
for (int bit = 0; bit < arr.length; bit++) {
if ((i & (1 << bit)) != 0) {
out.add(arr[bit]);
}
}
if (out.stream().mapToInt(e -> e.value).sum() <= maximumValue)
action.accept(out);
++i;
return true;
} else {
return false;
}
}
}, false);
}
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 + "]";
}
}
}
Result:
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=34]
Foo [type=2, value=15]
sum=49
Foo [type=2, value=39]
Foo [type=2, value=5]
sum=44
The only issue I see with this solution is, if you have duplicate value sets, then only result set is created. E.g.:
List<Foo> values = new ArrayList<>();
values.add(new Foo(1, 27));
values.add(new Foo(1, 13));
values.add(new Foo(1, 10));
values.add(new Foo(1, 27));
values.add(new Foo(1, 13));
values.add(new Foo(1, 10));
values.add(new Foo(1, 24));
values.add(new Foo(1, 18));
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, 5));
values.add(new Foo(2, 34));
values.add(new Foo(2, 15));
results in:
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=34]
Foo [type=2, value=15]
sum=49
Foo [type=2, value=39]
Foo [type=2, value=5]
sum=44
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | XtremeBaumer |