我正在尝试优化一个过程，即计算所有可能的玩家组合以形成分区。为了理解我的问题，我用下面的例子。例如，我们有一组玩家N = {1,2,3,4,5}，这些玩家像{1,2},{3,4},{5}一样重新组合。这意味着玩家1将与玩家2作为一名玩家进行游戏，因此也是一名玩家。每组玩家都有一套策略或选择。每个玩家选择自己想要加入的小组，例如：组CCD_ 3具有这些可能性CCD_；即玩家{1,2}要么选择呆在一起，要么选择加入组{3,4}。对其他玩家的解释相同：
{3,4}=>{{3,4};{3,4,5};{1,2,3,4}}
{5}=>{{5};{3,4,5}}
现在，选择相同策略的玩家将组成一个新的小组(联盟)。例如，{1,2}组选择了{1,2,3,4}策略；即玩家{1,2}想要与玩家{3,4}组成一个新的小组。玩家{3,4}选择策略{3,4,5}，玩家{5}选择策略{3,4,5}。选择了相同策略的玩家将在决赛中分组，形成这样的玩家分区：{1,2}，{3,4,5}；玩家3，4，5选择了相同的策略，所以他们分组在一起，玩家｛1，2｝选择了不同的策略，这样他们就可以单独呆着。我们对玩家策略的所有可能组合进行同样的处理，以获得基数为K的玩家的所有可能分区。在最后，我必须选择玩家的最优分区。在前面的例子中：我必须只生成基数为2的分区：|｛1,2,3,4｝，｛5｝|=2|｛1,2｝｛3,4,5｝|=3此分区是不允许的：|{1,2}{3,4}{5}|=3我已经将这个过程编程为递归函数，以获得玩家的所有可允许分区。这里的另一个问题是，我的函数生成了所有可能的分区，而我只得到了可允许的分区，这需要很多次！！
现在我的问题是，是否可以在java中使用并行性来计算播放器的所有可允许分区，尤其是当我们有很多播放器和这么多分区时。我必须做些什么才能加快一个大问题的执行？
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());
}
public static void main(String[] args) {
List<Set<Integer>> teams = asList(set(0,1,2), set(3,4), set(5),set(6,7,8),set(9,10,11),set(12,13,14));
Map<Set<Integer>, List<Set<Set<Integer>>>> team2Strategies = new HashMap<>();
team2Strategies.put(set(0,1,2), asList(set(set(0,1, 2)),
set(set(0,1, 2), set(3, 4))));
team2Strategies.put(set(3,4), asList(set(set(3, 4), set(5)),
set(set(0,1, 2), set(3, 4))));
team2Strategies.put(set(5), asList(set(set(5)),
set(set(3, 4), set(5)),set(set(5),set(6,7,8)),set(set(5),set(6,7,8),set(9,10,11),set(12,13,14))));
team2Strategies.put(set(6,7,8), asList(set(set(6,7,8)),
set(set(6, 7,8), set(5)),set(set(5),set(6,7,8),set(9,10,11),set(12,13,14))));
team2Strategies.put(set(9,10,11), asList(set(set(9,10,11)),
set(set(9, 10,11), set(12,13,14)),set(set(5),set(6,7,8),set(9,10,11),set(12,13,14))));
team2Strategies.put(set(12,13,14), asList(set(set(12,13,14)),
set(set(12, 13,14), set(9,10,11)),set(set(5),set(6,7,8),set(9,10,11),set(12,13,14))));
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();
};
//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")));
}
}
Java 8中的Stream类能够在可能的情况下自动并行执行操作。当然，为了实现这一点，重要的是，在可能并行运行的代码中，所有操作都必须是线程安全的。实现这一点的最简单方法是避免对变量或集合进行任何修改。这里有一个使用流的解决方案。它也只遍历每个可能的分区一次，并且应该是相当有效的。我将每个分区表示为一个策略列表。每个策略都是一个团队列表。每一个团队依次也是一个列表。这意味着团队列表可能如下所示：[[1,2], [3,4], [5]]一个策略可能是这样的[[3,4], [5]](意味着团队[3,4]和团队[5]配对)。分区可能是这样的[[[1,2]], [[3,4], [5]]]等于{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")));
}
}
该程序的输出为
{1, 2}{3, 4, 5}
{1, 2, 3, 4}{5}
编辑：
我必须单独代表每个团队才能使此策略发挥作用。但是您可以通过使用集合而不是列表来改进它。这样CCD_ 17将等于CCD_。集合还应该使整个程序更快。找到解决方案后，您可以将其转换为更好的形式，即将[[3,4],[5]]转换为[3,4,5]，并在处理时对数字进行排序。
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")));
}
}