Use parallelism to solve recursive function with Java

The Stream class in Java 8 can automatically perform operations in parallel if possible. Of course, for this it is important that within the code that can be executed in parallel, all operations must be thread safe. The easiest way to achieve this is to avoid any changes to variables or collections. Here is a solution that uses streams. It also only goes through every possible section once and should be quite effective. I presented each section as a list of strategies. Each strategy is a list of commands. Each team, in turn, is also a list. This means that the list of teams might look like this: the [[1,2], [3,4], [5]]

strategy might look like this: [[3,4], [5]]

(team [3,4]

and team [5]

pair up). And the section might look like this: [[[1,2]], [[3,4], [5]]]

which is{1,2}{3,4,5}

import static java.util.Arrays.asList;
import java.util.ArrayList;
import java.util.List;
import java.util.HashMap;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Test {
  static <T> List<List<List<T>>> calcPartitions(List<T> teams, Map<T, List<List<T>>> team2Strategies, int k, boolean doParallel) {
    if(k == 0) {
      if(teams.isEmpty()) return asList(new ArrayList<>());
      else return new ArrayList<>();
    } else if(teams.isEmpty()) {
      return new ArrayList<>();
    }

    T team = teams.get(0);
    Stream<List<T>> strategies = 
      (doParallel ? team2Strategies.get(team).parallelStream() : team2Strategies.get(team).stream())
        .filter(strategy ->
          strategy.stream().allMatch(team2 ->
            teams.contains(team2) && team2Strategies.get(team2).contains(strategy)));
      return strategies.flatMap(strategy -> {
        List<T> newTeams = new ArrayList<>(teams);
        newTeams.removeAll(strategy);
        List<List<List<T>>> restPartitions = calcPartitions(newTeams, team2Strategies, k - 1, false);
        for(List<List<T>> partition: restPartitions) {
          partition.add(0, strategy);
        }
        return restPartitions.stream();
      })
      .collect(Collectors.toList());
  }

  public static void main(String[] args) {
    List<List<Integer>> teams = asList(asList(1,2), asList(3,4), asList(5));

    Map<List<Integer>, List<List<List<Integer>>>> team2Strategies = new HashMap<>();

    team2Strategies.put(asList(1,2), asList(asList(asList(1, 2)),
                                            asList(asList(1, 2), asList(3, 4))));
    team2Strategies.put(asList(3,4), asList(asList(asList(3, 4)),
                                            asList(asList(3, 4), asList(5)),
                                            asList(asList(1, 2), asList(3, 4))));
    team2Strategies.put(asList(5), asList(asList(asList(5)),
                                          asList(asList(3, 4), asList(5))));

    List<List<List<List<Integer>>>> partitions = calcPartitions(teams, team2Strategies, 2, true);

    System.out.println(
      partitions.stream().map(partition ->
        partition.stream().map(strategy ->
          strategy.stream().map(team ->
            team.stream().map(i -> i.toString()).collect(Collectors.joining(", ")))
          .collect(Collectors.joining(", ", "{", "}")))
        .collect(Collectors.joining()))
      .collect(Collectors.joining("\n")));
  }
}

      

        
        
        
      

    

Output of this program

{1, 2}{3, 4, 5}
{1, 2, 3, 4}{5}

      

        
        
        
      

    

change

I have to represent each team individually for this strategy to work. But you can improve it by using sets instead of lists. Thus, it [[3,4],[5]]

will be equal [[5],[3,4]]

. The kits should also speed up the execution of the entire program. Once the solutions are found, you can then convert them to a nicer form, i.e. convert [[3,4],[5]]

to [3,4,5]

, and also sort the numbers while you are at it.

import static java.util.Arrays.asList;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Test {
  @SafeVarargs
  static <T> Set<T> set(T ... elems) {
    return new HashSet<T>(asList(elems));
  }

  static <T> List<Set<Set<T>>> calcPartitions(List<T> teams, Map<T, List<Set<T>>> team2Strategies, int k, boolean doParallel) {
    if(k == 0) {
      if(teams.isEmpty()) return asList(new HashSet<>());
      else return new ArrayList<>();
    } else if(teams.isEmpty()) {
      return new ArrayList<>();
    }

    Set<T> teamsSet = new HashSet<>(teams);

    T team = teams.get(0);
    Stream<Set<T>> strategies = 
      (doParallel ? team2Strategies.get(team).parallelStream() : team2Strategies.get(team).stream())
        .filter(strategy ->
          strategy.stream().allMatch(team2 ->
            teamsSet.contains(team2) && team2Strategies.get(team2).contains(strategy)));
      return strategies.flatMap(strategy -> {
        List<T> newTeams = new ArrayList<>(teams);
        newTeams.removeAll(strategy);
        List<Set<Set<T>>> restPartitions = calcPartitions(newTeams, team2Strategies, k - 1, false);
        for(Set<Set<T>> partition: restPartitions) {
          partition.add(strategy);
        }
        return restPartitions.stream();
      })
      .collect(Collectors.toList());
  }

  static List<Set<Integer>> teams = new ArrayList<>();
  static Map<Set<Integer>, List<Set<Set<Integer>>>> team2Strategies = new HashMap<>();

  private static Set<Integer> toSet(String string) {
    return Stream.of(string.split(" ")).map(s -> Integer.valueOf(s.trim())).collect(Collectors.toSet());
  }

  @SafeVarargs
  private static void defineTeams(List<String> ... definitions) {
    for(List<String> def: definitions) {
      teams.add(toSet(def.get(0)));
    }

    for(List<String> def: definitions) {
      Set<Integer> team = toSet(def.get(0));
      Stream<Set<Integer>> strategies = def.stream().skip(1).map(s -> toSet(s));
      List<Set<Set<Integer>>> startegiesList =
        strategies.map(strat -> teams.stream().filter(strat::containsAll).collect(Collectors.toSet()))
                  .collect(Collectors.toList());
      team2Strategies.put(team, startegiesList);
    }
  }

  public static void main(String[] args) {
    defineTeams(asList("0 1 2", "0 1 2", "0 1 2 3 4"),
                asList("3 4", "3 4 5", "0 1 2 3 4"),
                asList("5", "5", "3 4 5", "5 6 7 8", "5 6 7 8 9 10 11 12 13 14"),
                asList("6 7 8", "6 7 8", "5 6 7 8", "5 6 7 8 9 10 11 12 13 14"),             
                asList("9 10 11", "9 10 11", "9 10 11 12 13 14", "5 6 7 8 9 10 11 12 13 14"),
                asList("12 13 14", "12 13 14", "9 10 11 12 13 14", "5 6 7 8 9 10 11 12 13 14"));

    System.out.println("teams = "+ teams);
    System.out.println("team trategies = " + team2Strategies);
    System.out.println();

    List<Set<Set<Set<Integer>>>> partitions = calcPartitions(teams, team2Strategies, 3, true);

    Comparator<List<Integer>> intListComparator = (a, b) -> {
      int i = 0;
      while(i < a.size() && i < b.size()) {
        if(a.get(i) > b.get(i)) return 1;
        else if(a.get(i) < b.get(i)) return -1;
        i++;
      }
      return a.size() - b.size();
    };

    System.out.println(partitions);

    //in "partitions" a strategy was a Set<Set<Integer>>
    //in "partitionsList" however a strategy is a List<Integer>
    List<List<List<Integer>>> partitionsList =
      partitions.stream().map(partition ->
        partition.stream().map(strategy ->
          strategy.stream().flatMap(Set::stream)
                           .sorted()
                           .collect(Collectors.toList()))
        .sorted(intListComparator).collect(Collectors.toList()))
      .collect(Collectors.toList());

    System.out.println(partitionsList);

    System.out.println(
      partitionsList.stream().map(partition ->
        partition.stream().map(strategy ->
          strategy.stream().map(i -> i.toString()).collect(Collectors.joining(", ", "{", "}")))
        .collect(Collectors.joining()))
      .collect(Collectors.joining("\n")));
  }
}