Generate List with Combination of Subset of List, Java

Question

This question is to be implemented in Java.

I have a class named Competitor, with Type, Name and Power.

public class Competitor {
  private final int type;
  private final String name;
  private final int power;

  public Competitor(int type, String name, int power) {
    this.type = type;
    this.name = name;
    this.power = power;
  }

  public int getType() {
    return type;
  }

  public String getName() {
    return name;
  }

  public int getPower() {
    return power;
  }

  @Override
  public String toString() {
    return "Competitor{" + "type=" + type + ", name=" + name + ", power=" + power + '}';
  }

}

Now, I want to do a game, with ONE competitor by type, the numbers of type can be 60 (3D arrays or nested for is not a solution for me).

I want to generate all posible combination of sub Set (classified by type) of this List.

public class Game {
  public static void main(String... args) {
    List<Competitor> listCompetitors = new ArrayList<>();
    listCompetitors.add(new Competitor(1, "Cat 00", 93));
    listCompetitors.add(new Competitor(1, "Cat 10", 11));
    listCompetitors.add(new Competitor(1, "Cat 23", 20));

    listCompetitors.add(new Competitor(2, "Dog 61", 54));
    listCompetitors.add(new Competitor(2, "Dog 18", 40));
    listCompetitors.add(new Competitor(2, "Dog 45", 71));
    listCompetitors.add(new Competitor(2, "Dog 30", 68));

    listCompetitors.add(new Competitor(3, "Pig 90", 90));
    listCompetitors.add(new Competitor(3, "Pig 78", 32));

    listCompetitors.add(new Competitor(4, "Cow 99", 90));

    // The type is NOT fixed number (is variable from 1 to 60)
  }
}

How is possible generate the combination like...

new Competitor(1, "Cat 00", 93)
new Competitor(2, "Dog 61", 54)
new Competitor(3, "Pig 90", 90)
new Competitor(4, "Cow 99", 90)

Another combination

new Competitor(1, "Cat 00", 93)
new Competitor(2, "Dog 61", 54)
new Competitor(3, "Pig 78", 32)
new Competitor(4, "Cow 99", 90)

...

The last combination

new Competitor(1, "Cat 23", 20)
new Competitor(2, "Dog 30", 68)
new Competitor(3, "Pig 78", 32)
new Competitor(4, "Cow 99", 90)

How generate sublist like proposed before?

I also raise the bet.

Taking in account the power parameter. What is are the List<Competitor> the worse(minimum sum of power) and best (maximum sum of parameter) performance?

Answer 1

First, group all elements by type, to get the lists to combine.

Map<Integer, List<Competitor>> map
    = listCompetitors.stream().collect(Collectors.groupingBy(Competitor::getType));

Then, to build the Cartesian Product, we need a helper method to create a new List out of an existing List and an additional element. Unfortunately, there’s no built-in method for that (but you might find such operations in 3rd party libraries though)

static <T> List<T> listWith(List<T> list, T t) {
    List<T> result = new ArrayList<>(list.size() + 1);
    result.addAll(list);
    result.add(t);
    return result;
}

With that, we can construct a Stream and collect it into a result List:

Stream<List<Competitor>> stream = Stream.of(Collections.emptyList());
for(List<Competitor> next: map.values())
    stream = stream.flatMap(list -> next.stream().map(c -> listWith(list, c)));

List<List<Competitor>> listOfListCompetitor = stream.collect(Collectors.toList());

Each flatMap step will combine the stream with another dimension.

The collection operation of listWith could also be done with another stream operation, e.g.

Stream<List<Competitor>> stream = Stream.of(Collections.emptyList());
for(List<Competitor> next: map.values())
    stream = stream.flatMap(list -> next.stream()
        .map(c -> Stream.concat(list.stream(), Stream.of(c)).collect(Collectors.toList())));

List<List<Competitor>> listOfListCompetitor = stream.collect(Collectors.toList());

but that’s not as intuitive, imho.