Outputting permutations of ArrayList using recursion

Question

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.

Here is my code:

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);
        }
    }
}

The input is:

Julia Lucas Mia -1

The output is supposed to be:

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

But mine is:

Julia Julia Julia 
Lucas Lucas Lucas 
Mia Mia Mia

score 1 · Accepted Answer · 2021-04-25 10:50:41Z

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);

Intermediate output:

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

Final output:

{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}

^{See also: String permutations using recursion in Java}

James Mudd · Accepted Answer · 2021-06-03 08:20:59Z

0

Just another option if your looking at permutations, it might be better to use a library. Guava has a function for this Collections2#permutations and you can look at the implementation here.

answered Jun 3, 2021 at 8:20

James Mudd

2,4931 gold badge27 silver badges38 bronze badges

Collectives™ on Stack Overflow

Outputting permutations of ArrayList using recursion

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related