如何从LinkedHashMap>的值中进行组合

huangapple go评论85阅读模式
英文:

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&lt;List&lt;String&gt;&gt; getCombinations(ArrayList&lt;ArrayList&lt;String&gt;&gt; valueSetList) {
    int comboCount = 1;
    for (List&lt;String&gt; valueSet : valueSetList)
        comboCount = Math.multiplyExact(comboCount, valueSet.size()); // Fail if overflow
    ArrayList&lt;List&lt;String&gt;&gt; combinations = new ArrayList&lt;&gt;(comboCount);
    for (int comboNumber = 0; comboNumber &lt; comboCount; comboNumber++) {
        List&lt;String&gt; combination = new ArrayList&lt;&gt;(valueSetList.size());
        int remain = comboNumber;
        for (List&lt;String&gt; 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&#39;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&lt;List&lt;Integer&gt;&gt; merge(List&lt;List&lt;List&lt;Integer&gt;&gt;&gt; lists) {
    List&lt;List&lt;Integer&gt;&gt; resultLists = new ArrayList&lt;&gt;();
    if (lists.size() == 0) {
        resultLists.add(new ArrayList&lt;&gt;());
    } else {
        List&lt;List&lt;Integer&gt;&gt; firstList = lists.get(0);
        List&lt;List&lt;Integer&gt;&gt; remainingLists = merge(lists.subList(1, lists.size()));
        for (List&lt;Integer&gt; first : firstList) {
            for (List&lt;Integer&gt; remaining : remainingLists) {
                List&lt;Integer&gt; resultList = new ArrayList&lt;&gt;();
                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&lt;String, List&lt;List&lt;Integer&gt;&gt;&gt; map) {
    System.out.println(&quot;input map: &quot; + map);
    
    List&lt;List&lt;Integer&gt;&gt; list = merge(new ArrayList&lt;&gt;(map.values()));
    
    list.forEach(System.out::println);
}

// --------
Map&lt;String, List&lt;List&lt;Integer&gt;&gt;&gt; map1 = new LinkedHashMap&lt;&gt;();

map1.put(&quot;SFO&quot;, Arrays.asList(Arrays.asList(1)));
map1.put(&quot;SEA&quot;, Arrays.asList(Arrays.asList(2), Arrays.asList(3), Arrays.asList(4)));
map1.put(&quot;PHX&quot;, Arrays.asList(Arrays.asList(5), Arrays.asList(6)));

testCombinations(map1);
        
Map&lt;String, List&lt;List&lt;Integer&gt;&gt;&gt; map2 = new LinkedHashMap&lt;&gt;();

map2.put(&quot;FRA&quot;, Arrays.asList(Arrays.asList(1, 2), Arrays.asList(3, 4)));
map2.put(&quot;MEL&quot;, 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 &lt;T extends List&gt; Stream&lt;List&lt;T&gt;&gt; ofCombinations(List&lt;? extends Collection&lt;T&gt;&gt; mapValues, List&lt;T&gt; current) {
    return mapValues.isEmpty() ? Stream.of(current) :
        mapValues.get(0).stream().flatMap(list -&gt; {
            List&lt;T&gt; combination = new ArrayList&lt;T&gt;(current);
            combination.addAll(list);
            return ofCombinations(mapValues.subList(1, mapValues.size()), combination);
        });
}

private static void testStreamCombinations(Map&lt;String, List&lt;List&lt;Integer&gt;&gt;&gt; map) {
    System.out.println(&quot;input map: &quot; + map);
    
    ofCombinations(new ArrayList&lt;&gt;(map.values()), Collections.emptyList())
        .forEach(System.out::println);   
}

// invoking test method
testStreamCombinations(map1);
testStreamCombinations(map2);

Test output: same as above.

huangapple
  • 本文由 发表于 2020年10月26日 00:01:33
  • 转载请务必保留本文链接:https://go.coder-hub.com/64525776.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定