英文:
How to make combination from values of of LinkedHashMap<String, ArrayList<ArrayList>>
问题
public static ArrayList<ArrayList<String>> getCombinations(ArrayList<ArrayList<String>> valueSetList) {
int comboCount = 1;
for (ArrayList<String> valueSet : valueSetList)
comboCount = Math.multiplyExact(comboCount, valueSet.size());
ArrayList<ArrayList<String>> combinations = new ArrayList<>(comboCount);
for (int comboNumber = 0; comboNumber < comboCount; comboNumber++) {
ArrayList<String> combination = new ArrayList<>(valueSetList.size());
int remain = comboNumber;
for (ArrayList<String> valueSet : valueSetList) {
combination.add(valueSet.get(remain % valueSet.size()));
remain /= valueSet.size();
}
combinations.add(combination);
}
return combinations;
}
Note: I have only translated the code part as requested. If you have any questions or need further assistance, feel free to ask.
英文:
Suppose we have below LinkedHashMap<String, ArrayList<ArrayList<String>>>
{FRA=[[1, 2], [3, 4]], MEL=[[5, 6]]}
The output should be
[1,2,5,6], [3,4,5,6]
Similarly if input is :
{SFO=[[1]], SEA=[[2], [3], [4]], PHX=[[5], [6]]}
Then expected output is
[1,2,5],[1,2,6],[1,3,5],[1,3,6],[1,4,5],[1,4,6]
I have tried below code , but did not get the expected result.
public static ArrayList<List<String>> getCombinations(ArrayList<ArrayList<String>> valueSetList) {
int comboCount = 1;
for (List<String> valueSet : valueSetList)
comboCount = Math.multiplyExact(comboCount, valueSet.size()); // Fail if overflow
ArrayList<List<String>> combinations = new ArrayList<>(comboCount);
for (int comboNumber = 0; comboNumber < comboCount; comboNumber++) {
List<String> combination = new ArrayList<>(valueSetList.size());
int remain = comboNumber;
for (List<String> valueSet : valueSetList) {
combination.add(valueSet.get(remain % valueSet.size()));
remain /= valueSet.size();
}
combinations.add(combination);
}
return combinations;
}
Any help is highly appreciated.
答案1
得分: 0
以下是您提供的内容的翻译部分：
以下是基于[Philipp Meister的回答](https://stackoverflow.com/a/9496234/13279831)的递归解决方案，类似问题是关于构建[笛卡尔积](https://en.wikipedia.org/wiki/Cartesian_product)的：
```java
static List<List<Integer>> merge(List<List<List<Integer>>> lists) {
List<List<Integer>> resultLists = new ArrayList<>();
if (lists.size() == 0) {
resultLists.add(new ArrayList<>());
} else {
List<List<Integer>> firstList = lists.get(0);
List<List<Integer>> remainingLists = merge(lists.subList(1, lists.size()));
for (List<Integer> first : firstList) {
for (List<Integer> remaining : remainingLists) {
List<Integer> resultList = new ArrayList<>();
resultList.addAll(first);
resultList.addAll(remaining);
resultLists.add(resultList);
}
}
}
return resultLists;
}
主要区别在于返回类型以及根据要求将first列表的所有元素添加到嵌套列表中。
测试设置
private static void testCombinations(Map<String, List<List<Integer>>> map) {
System.out.println("输入映射: " + map);
List<List<Integer>> list = merge(new ArrayList<>(map.values()));
list.forEach(System.out::println);
}
// --------
Map<String, List<List<Integer>>> map1 = new LinkedHashMap<>();
map1.put("SFO", Arrays.asList(Arrays.asList(1)));
map1.put("SEA", Arrays.asList(Arrays.asList(2), Arrays.asList(3), Arrays.asList(4)));
map1.put("PHX", Arrays.asList(Arrays.asList(5), Arrays.asList(6)));
testCombinations(map1);
Map<String, List<List<Integer>>> map2 = new LinkedHashMap<>();
map2.put("FRA", Arrays.asList(Arrays.asList(1, 2), Arrays.asList(3, 4)));
map2.put("MEL", Arrays.asList(Arrays.asList(5, 6)));
testCombinations(map2);
输出:
输入映射: {SFO=[[1]], SEA=[[2], [3], [4]], PHX=[[5], [6]]}
[1, 2, 5]
[1, 2, 6]
[1, 3, 5]
[1, 3, 6]
[1, 4, 5]
[1, 4, 6]
输入映射: {FRA=[[1, 2], [3, 4]], MEL=[[5, 6]]}
[1, 2, 5, 6]
[3, 4, 5, 6]
可以使用流和递归的flatMap链来实现解决方案（基于Marco13的回答的基础上）：
static <T extends List> Stream<List<T>> ofCombinations(List<? extends Collection<T>> mapValues, List<T> current) {
return mapValues.isEmpty() ? Stream.of(current) :
mapValues.get(0).stream().flatMap(list -> {
List<T> combination = new ArrayList<T>(current);
combination.addAll(list);
return ofCombinations(mapValues.subList(1, mapValues.size()), combination);
});
}
private static void testStreamCombinations(Map<String, List<List<Integer>>> map) {
System.out.println("输入映射: " + map);
ofCombinations(new ArrayList<>(map.values()), Collections.emptyList())
.forEach(System.out::println);
}
// 调用测试方法
testStreamCombinations(map1);
testStreamCombinations(map2);
测试输出：与上面相同。
<details>
<summary>英文:</summary>
The following recursive solution is based on [Philipp Meister's answer](https://stackoverflow.com/a/9496234/13279831) to similar question about building of the [Cartesian product](https://en.wikipedia.org/wiki/Cartesian_product):
```java
static List<List<Integer>> merge(List<List<List<Integer>>> lists) {
List<List<Integer>> resultLists = new ArrayList<>();
if (lists.size() == 0) {
resultLists.add(new ArrayList<>());
} else {
List<List<Integer>> firstList = lists.get(0);
List<List<Integer>> remainingLists = merge(lists.subList(1, lists.size()));
for (List<Integer> first : firstList) {
for (List<Integer> remaining : remainingLists) {
List<Integer> resultList = new ArrayList<>();
resultList.addAll(first);
resultList.addAll(remaining);
resultLists.add(resultList);
}
}
}
return resultLists;
}
Main difference is in the return type and adding all elements of the first list to the nested list according to the requirements.
Test setup
private static void testCombinations(Map<String, List<List<Integer>>> map) {
System.out.println("input map: " + map);
List<List<Integer>> list = merge(new ArrayList<>(map.values()));
list.forEach(System.out::println);
}
// --------
Map<String, List<List<Integer>>> map1 = new LinkedHashMap<>();
map1.put("SFO", Arrays.asList(Arrays.asList(1)));
map1.put("SEA", Arrays.asList(Arrays.asList(2), Arrays.asList(3), Arrays.asList(4)));
map1.put("PHX", Arrays.asList(Arrays.asList(5), Arrays.asList(6)));
testCombinations(map1);
Map<String, List<List<Integer>>> map2 = new LinkedHashMap<>();
map2.put("FRA", Arrays.asList(Arrays.asList(1, 2), Arrays.asList(3, 4)));
map2.put("MEL", Arrays.asList(Arrays.asList(5, 6)));
testCombinations(map2);
Output:
input map: {SFO=[[1]], SEA=[[2], [3], [4]], PHX=[[5], [6]]}
[1, 2, 5]
[1, 2, 6]
[1, 3, 5]
[1, 3, 6]
[1, 4, 5]
[1, 4, 6]
input map: {FRA=[[1, 2], [3, 4]], MEL=[[5, 6]]}
[1, 2, 5, 6]
[3, 4, 5, 6]
The solution may be implemented using streams and recursive flatMap chain (on the basis of Marco13's answer):
static <T extends List> Stream<List<T>> ofCombinations(List<? extends Collection<T>> mapValues, List<T> current) {
return mapValues.isEmpty() ? Stream.of(current) :
mapValues.get(0).stream().flatMap(list -> {
List<T> combination = new ArrayList<T>(current);
combination.addAll(list);
return ofCombinations(mapValues.subList(1, mapValues.size()), combination);
});
}
private static void testStreamCombinations(Map<String, List<List<Integer>>> map) {
System.out.println("input map: " + map);
ofCombinations(new ArrayList<>(map.values()), Collections.emptyList())
.forEach(System.out::println);
}
// invoking test method
testStreamCombinations(map1);
testStreamCombinations(map2);
Test output: same as above.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论