如何使用 Java 流制作列表元素的所有变体？

Question

我有一个列表，例如：

["a", "b", "c"]

我想创建列表列表，这些列表将是此列表元素的变体。结果应该是这样的：

[["a"], 
 ["b"], 
 ["c"], 
 ["a", "b"], 
 ["a", "c"], 
 ["b", "a"], 
 ["b", "c"], 
 ["c", "a"], 
 ["c", "b"], 
 ["a", "b", "c"], 
 ["a", "c", "b"], 
 ["b", "a", "c"], 
 ["b", "c", "a"], 
 ["c", "a", "b"], 
 ["c", "b", "a"]]

如果解决方案将使用 java 流，则最好（但不是必需）。

我正在尝试这样的事情：

List<List<String>> lists = IntStream.rangeClosed(1, list.size()) //size of sublist
.flatMap(i -> list.subList(0, i).stream()).collect(Collectors.toList())

但它不起作用。

Answer 1

你需要做的是利用k-置换。您需要对传递的数组的每个长度执行此 k 排列以获得所有可能的变化。

代码:

private static List<List<String>> getAllVariations(List<String> elements){
    return IntStream.rangeClosed(1, elements.size()).boxed()
            .flatMap(i-> kPermutate(elements,0,i).stream())
            .collect(Collectors.toList());
}

private static List<List<String>> kPermutate(List<String> allElements, int i, int numberOfElements)
{
    if(i == numberOfElements)
    {
        //New ArrayList because we want a clone of the sublist
        return Arrays.asList(new ArrayList<>(allElements.subList(0, numberOfElements)));
    }
    List<List<String>> tempResult = new ArrayList<>();

    for(int j=i; j<allElements.size(); j++)
    {
        Collections.swap(allElements, i, j);
        tempResult.addAll(kPermutate(allElements, i+1, numberOfElements));
        Collections.swap(allElements, i, j);
    }
    return tempResult;
}

测试：

public static void main(String[] args) {
    List<String> elements = Arrays.asList("a", "b", "c");

    List<List<String>> result = getAllVariations(elements);

    System.out.println(result);
}

输出：

[[a], [b], [c], [a, b], [a, c], [b, a], [b, c], [c, b], [c, a], [a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, b, a], [c, a, b]]

如果您不想在 getAllVariations 方法中使用流，您也可以像这样将其实现为常规 for 循环

private static List<List<String>> getAllVariations(List<String> elements){
    List<List<String>> result = new ArrayList<>();
    //Start from 1 because we don't want to include [] in the list.
    //i<=elements.size(): we use <= because we want the max number of permutations. this is not a 0 based index for that
    for(int i=1;i<=elements.size();i++){
        result.addAll(kPermutate(elements,0,i));
    }
    return result;
}

如何使用 Java 流制作列表元素的所有变体？

How to make all variations of list elements using Java streams?

java

combinatorics

java-stream