Permutation of Strings within an ArrayList (Using Recursion)

Ive been trying to figure this out for awhile now and just cant quite understand how im meant to create the expected outputs. Ive managed to get the input and maximum number of Unique permutations, all i need now is to find out how to get the expected strings as outputs. Im assuming that there is a better way to go about doing this.

Input:
Julia Lucas Mia -1

Expected Output:

Julia, Lucas, Mia

Julia, Mia, Lucas

Lucas, Julia, Mia

Lucas, Mia, Julia

Mia, Julia, Lucas

Mia, Lucas, Julia

import java.util.Scanner;
import java.util.ArrayList;

public class PhotoLineups {

    // TODO: Write method to create and output all permutations of the list of names.
        public static void printAllPermutations(ArrayList<String> permList, ArrayList<String> nameList){
        int size = nameList.size();
        int index = 0;

        for(int i = size; i > 1; i--)
            size = size * (i - 1);
        System.out.println("Size: " +size); //Temp

        if(index != size){
            for(int i = 0; i < nameList.size(); i++){
                
                index++;
            }
        }
    }

    public static void main(String[] args){
        Scanner scnr = new Scanner(System.in);
        ArrayList<String> nameList = new ArrayList<String>();
        ArrayList<String> permList = new ArrayList<String>();
        String name;
        int i = 0;
        
        // TODO: Read in a list of names; stop when -1 is read. Then call recursive method.
        while(i != -1){
            name = scnr.next();
            nameList.add(name);
            if(name.equals("-1"))
                i = -1;
        }
        nameList.remove(nameList.size() - 1);
        System.out.println("nameList: " + nameList); //Temp

        //Recursive
        printAllPermutations(permList, nameList);
    }
}

>Solution :

Recursion in this case means to split the Problem in one step and the Rest.
So the Algorithm would be pick in a loop the names of the list and combine this with the permutations of the rest. If the rest is empty, you got a permutation:
You got to copy the List since they are passed by reference…

public static void printAllPermutations(ArrayList<String> permList, ArrayList<String> nameList){

    if (nameList.isEmpty()) {
        System.out.println(String.join(", ", permList));
        return;
    }

    for(int i = 0; i < nameList.size(); i++) {
        ArrayList<String> localPermList = new ArrayList<>(permList);
        ArrayList<String> localNameList = new ArrayList<>(nameList);
        localPermList.add(nameList.get(i));
        localNameList.remove(nameList.get(i));
        printAllPermutations(localPermList, localNameList);

    }

}

Leave a Reply