Permutations of Strings in an Array need to be in same order but aren't

Question

Using recursion to print all permutations of strings of names in an ArrayList, need them to be in a specific order, some lines are correct then some near the ends of switching the first word of the permutations mess up. For example index wise, it needs to be 3,1,2 then 3,2,1 however it's reverse.

My Output:

• Julia Lucas Mia
• Julia Mia Lucas
• Lucas Julia Mia
• Lucas Mia Julia
• Mia Lucas Julia
• Mia Julia Lucas

Expected Output:

• Julia Lucas Mia
• Julia Mia Lucas
• Lucas Julia Mia
• Lucas Mia Julia
• Mia Julia Lucas
• Mia Lucas Julia (This line the one above need to be swapped)

   public static void allPermutations(ArrayList<String> permList, ArrayList<String> nameList, 
   int index) {
      
      if (index == nameList.size() - 1) {
         for (int i = 0; i < nameList.size(); i++) {
            permList.add(nameList.get(i));
         }
         for (String val: permList) {
            System.out.print(val + " ");
         }
         System.out.println();
         permList.clear();
         
      } 
      for (int i = index; i < nameList.size(); i++) {
         Collections.swap(nameList, index, i);
         allPermutations(permList, nameList, index + 1);
         Collections.swap(nameList, index, i);
      }
         
      }
      
   }

   public static void main(String[] args) {
      Scanner scnr = new Scanner(System.in);
      ArrayList<String> nameList = new ArrayList<String>();
      ArrayList<String> permList = new ArrayList<String>();

      nameList.add("Julia");
      nameList.add("Lucas");
      nameList.add("Mia ");
      
      
      allPermutations(permList, nameList, 0);
      
   }

Answer 1

Assumptions

1. Iterative code is allowed

Logic

1. Initialize string array and an corresponding integer array to maintain the order of original elements
2. Iteratively compute the next permutation

Next Permutation

1. Scan the given input in reverse order
2. Find the pivot index where value[pivot] < value[pivot + 1]
3. All the entries to the right of pivot are in descending order
4. For a given permutation, the next permutation will be a immediate bigger value (if thought numerically)
5. eg: 1234 -> 1243 -> 1324 -> 1342
6. Find the element just bigger than pivot element (on right side)
7. swap these two elements
8. Still all the elements to the right of pivot index are in descending order
9. reverse elements from pivot + 1 to end (make the ascending order)
10. this is the next permutation

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Permutation {

    // iteratively compute all permutaions
    private static void permute(String[] permutation, Integer[] order) {
        boolean hasMore;
        do {
            System.out.println(Arrays.deepToString(permutation));
            hasMore = next(permutation, order);
        } while (hasMore);
    }

    // given a permutation, find the next permutation based on the order
    private static boolean next(String[] permutation, Integer[] order) {
        int pivot = order.length - 2;
        // check from last and find the first left index greater than its next right index
        while (pivot >= 0 && order[pivot + 1] < order[pivot]) {
            pivot--;
        }

        // if reached beginning, then completed
        if (pivot < 0) {
            return false;
        }

        // find the index of least bigger element on the right
        int swap = pivot + 1;
        while (swap < order.length && order[pivot] < order[swap]) {
            swap++;
        }
        swap--;

        // swap pivot and its least bigger elemment
        swap(order, swap, pivot);
        swap(permutation, swap, pivot);

        // reverse the descending part after pivot and turn into ascending
        reverse(order, pivot + 1, order.length - 1);
        reverse(permutation, pivot + 1, permutation.length - 1);

        return true;
    }

    private static <T> void reverse(T[] a, int left, int right) {
        while (left < right) {
            swap(a, left++, right--);
        }
    }

    private static <T> void swap(T[] a, int i, int j) {
        T temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        List<String> nameList = new ArrayList<>();

        nameList.add("Julia");
        nameList.add("Lucas");
        nameList.add("Mia");

        String[] permutation = nameList.toArray(new String[nameList.size()]);
        Integer[] order = IntStream.range(0, nameList.size()).boxed()
            .collect(Collectors.toList()).toArray(new Integer[nameList.size()]);
        permute(permutation, order);
    }
}

Answer 2

If you want the expected answer which you have shown then you can try my code ->

static void permutate(ArrayList<String> ar, String ans, boolean b[], int v) {
    if (v == 3) {
        System.out.println(ans);
        return;
    }
    for (int i = 0; i < ar.size(); i++) {
        if (b[i] == false) {
            b[i] = true;
            permutate(ar, ans + ar.get(i) + "  ", b, v + 1);
            b[i] = false;
        }
    }
}

public static void main(String[] args) {
    ArrayList<String> ar = new ArrayList<>();
    ar.add("Julia ");
    ar.add("Lucas ");
    ar.add("Mia ");
    permutate(ar, "", new boolean[4], 0);
}