Создать список с комбинацией подмножества списка, Java

Question

Этот вопрос должен быть реализован на Java.

У меня есть класс с именем Конкурент, с типом, именем и силой.

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 + '}';
  }

}

Теперь я хочу сделать игру с ОДНИМ конкурентом на type, число типа может быть 60 (3D arrays или вложенное for для меня не решение).

Я хочу сгенерировать все возможные комбинации поднабора (классифицированные по типу) этого списка.

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)
  }
}

Как можно сгенерировать комбинацию типа ...

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

Другая комбинация

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

...

Последняя комбинация

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

Как создать подсписок, как предлагалось ранее?

Я также поднимаю ставку.

С учетом параметра мощности. Каковы List<Competitor> худшие (минимальная сумма мощности) и лучшие (максимальная сумма параметров) показатели?

Answer 1

Сначала сгруппируйте все элементы по типу, чтобы объединить списки.

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

Затем, чтобы построить декартово произведение, нам понадобится вспомогательный метод для создания нового List из существующего List и дополнительного элемента. К сожалению, для этого нет встроенного метода (но вы можете найти такие операции в сторонних библиотеках)

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;
}

С этим мы можем построить Stream и собрать его в результат 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());

Каждый шаг flatMap объединяет поток с другим измерением.

Операция сбора listWith также может быть выполнена с другой потоковой операцией, например,

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());

но это не так интуитивно понятно, имхо.

Answer 2

Я считаю, что решить вопрос

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));

    List<Integer> typeList = new ArrayList<>(listCompetitors.stream()
        .map(Competitor::getType)
        .collect(Collectors.toSet()));
    int sizeLimit = typeList.size();

    List<List<Competitor>> listOfListCompetitor = new ArrayList<>();
    getListCompetitorCombination(new ArrayList<>(), listCompetitors, sizeLimit, listOfListCompetitor);

    listOfListCompetitor.stream().forEach(listCompetitor -> {
      System.out.println("");
      listCompetitor.stream().sorted(Comparator.comparing(Competitor::getType)).forEach(System.out::print);
    });
    System.out.println();

  }

  public static List<Competitor> getListCompetitorCombination(List<Competitor> processed, List<Competitor> sublistCompetitor, int sizeLimit, List<List<Competitor>> outCompetitor) {
    List<Competitor> listCompetitorCombination = new ArrayList<>();

    /*
    List<Integer> typeList = new ArrayList<>(sublistCompetitor.stream()
        .map(Competitor::getType)
        .collect(Collectors.toSet()));
    */
    int type = sublistCompetitor.get(0).getType();//typeList.stream().findFirst().orElse(0);

    List<Competitor> listCompetitorsIncludeType = sublistCompetitor
        .stream()
        .filter(competitor -> competitor.getType() == type)
        .collect(Collectors.toList());

    List<Competitor> listCompetitorsExcludeType = sublistCompetitor
        .stream()
        .filter(competitor -> competitor.getType() != type)
        .collect(Collectors.toList());

    listCompetitorsIncludeType.stream().forEach(
        competitor
        -> {

      List<Competitor> newProcessed = new ArrayList<>(processed);
      newProcessed.add(0, competitor);
      if (sizeLimit == newProcessed.size()) {
        outCompetitor.add(newProcessed);
      } else {
        getListCompetitorCombination(newProcessed, listCompetitorsExcludeType, sizeLimit, outCompetitor);
      }
    });
    return listCompetitorCombination;
  }

}

Мой вывод

    debug:

    Competitor{type=1, name=Cat 00, power=93} Competitor{type=2, name=Dog 61, power=54} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 00, power=93} Competitor{type=2, name=Dog 61, power=54} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 00, power=93} Competitor{type=2, name=Dog 18, power=40} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 00, power=93} Competitor{type=2, name=Dog 18, power=40} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 00, power=93} Competitor{type=2, name=Dog 45, power=71} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 00, power=93} Competitor{type=2, name=Dog 45, power=71} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 00, power=93} Competitor{type=2, name=Dog 30, power=68} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 00, power=93} Competitor{type=2, name=Dog 30, power=68} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 10, power=11} Competitor{type=2, name=Dog 61, power=54} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 10, power=11} Competitor{type=2, name=Dog 61, power=54} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 10, power=11} Competitor{type=2, name=Dog 18, power=40} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 10, power=11} Competitor{type=2, name=Dog 18, power=40} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 10, power=11} Competitor{type=2, name=Dog 45, power=71} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 10, power=11} Competitor{type=2, name=Dog 45, power=71} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 10, power=11} Competitor{type=2, name=Dog 30, power=68} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 10, power=11} Competitor{type=2, name=Dog 30, power=68} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 23, power=20} Competitor{type=2, name=Dog 61, power=54} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 23, power=20} Competitor{type=2, name=Dog 61, power=54} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 23, power=20} Competitor{type=2, name=Dog 18, power=40} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 23, power=20} Competitor{type=2, name=Dog 18, power=40} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 23, power=20} Competitor{type=2, name=Dog 45, power=71} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 23, power=20} Competitor{type=2, name=Dog 45, power=71} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 23, power=20} Competitor{type=2, name=Dog 30, power=68} Competitor{type=3, name=Pig 90, power=90} Competitor{type=4, name=Cow 99, power=90} 
    Competitor{type=1, name=Cat 23, power=20} Competitor{type=2, name=Dog 30, power=68} Competitor{type=3, name=Pig 78, power=32} Competitor{type=4, name=Cow 99, power=90} 
    BUILD SUCCESSFUL (total time: 1 second)

Теперь, Может кто-нибудь предложить другое оптимизированное решение?