0

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
Community
  • 1
  • 1
Allen B
  • 15
  • 1
  • 5

2 Answers2

1

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

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.

James Mudd
  • 1,816
  • 1
  • 20
  • 25