使用递归输出 ArrayList 的排列 [英] Outputting permutations of ArrayList using recursion

问题描述

我正在尝试排列 ArrayList 中的项目.我没有得到正确的输出.我不知道问题是什么，我相信它在 allPermutations 方法的else"循环中.该列表添加所有字符串，直到输入为 -1.对不起，如果这是一个典型的问题，我在问之前尝试过查看这里但找不到任何帮助.

I am trying to permutate the items in an ArrayList. I'm not getting the right output. I don't know what the issue is, I believe it's in the 'else' loop in the allPermutations method. The list adds all strings until the input is -1. Sorry if this is a typical question, I tried looking on here before asking but couldn't find any help for myself.

这是我的代码:

public static void allPermutations(ArrayList<String> permList,
                                   ArrayList<String> nameList) {
    // base case
    // nameList is empty after performing all permutations
    if (nameList.size() == 0) {
        for (int i = 0; i < permList.size(); ++i) {
            for (int j = 0; j < permList.size(); ++j) {
                System.out.print(permList.get(i) + " ");
            }
            System.out.println();
        }
    } else {
        for (int i = 0; i < nameList.size(); ++i) {
            ArrayList<String> tempPerm = new ArrayList<>(permList);
            String name = nameList.get(i);

            // remove from nameList and add to new perm
            nameList.remove(i);
            tempPerm.add(name);

            allPermutations(tempPerm, nameList);
        }
    }
}

输入是:

Julia Lucas Mia -1

输出应该是:

Julia Lucas Mia 
Julia Mia Lucas 
Lucas Julia Mia 
Lucas Mia Julia 
Mia Julia Lucas 
Mia Lucas Julia 

但我的是:

Julia Julia Julia 
Lucas Lucas Lucas 
Mia Mia Mia 

推荐答案

您可以使用 Stream.reduce 方法作为一种递归.此解决方案假设原始数组可能包含重复项，如果没有，它也有效.

You can use Stream.reduce method as a kind of recursion. This solution assumes that the original array may contain duplicates, and it also works if there are none.

String[] strings = {"Julia", "Lucas", "Mia"};

IntStream.range(0, strings.length)
        // represent a 1d array 'n' as a 2d matrix 'n×n'
        .mapToObj(i -> IntStream.range(0, strings.length)
                // represent each string as Map<Integer,String>
                .mapToObj(j -> Map.of(j, strings[j]))
                // Stream<List<Map<Integer,String>>>
                .collect(Collectors.toList()))
        // intermediate output
        .peek(System.out::println)
        // reduce a stream of lists to a single list
        .reduce((list1, list2) -> list1.stream()
                // summation of pairs of maps from two lists
                .flatMap(map1 -> list2.stream()
                        // filter out those keys that are already present
                        .filter(map2 -> map2.keySet().stream()
                                .noneMatch(map1::containsKey))
                        // join entries of two maps
                        .map(map2 -> {
                            Map<Integer, String> map = new LinkedHashMap<>();
                            map.putAll(map1);
                            map.putAll(map2);
                            return map;
                        }))
                // collect into a single list
                .collect(Collectors.toList()))
        // List<Map<Integer,String>>
        .orElse(Collections.emptyList())
        // final output
        .forEach(System.out::println);

中间输出:

[{0=Julia}, {1=Lucas}, {2=Mia}]
[{0=Julia}, {1=Lucas}, {2=Mia}]
[{0=Julia}, {1=Lucas}, {2=Mia}]

最终输出:

{0=Julia, 1=Lucas, 2=Mia}
{0=Julia, 2=Mia, 1=Lucas}
{1=Lucas, 0=Julia, 2=Mia}
{1=Lucas, 2=Mia, 0=Julia}
{2=Mia, 0=Julia, 1=Lucas}
{2=Mia, 1=Lucas, 0=Julia}

---

^{另见:Java 中使用递归的字符串排列}

这篇关于使用递归输出 ArrayList 的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！