Как понять решение задачи по нахождению всех анаграмм (рекурсия)?

Question

[gleendo]

Есть рекурсивное решение задачи по нахождению всех анаграмм.
Помогите пожалуйста разобраться в решение. овер много времени сижу, не могу разобраться что к чему.

import java.util.Arrays;

public class Permutator {
    public static void perm(int[] arr, int size){
        if( size < 2){
            System.out.println(Arrays.toString(arr));
        } else { 
            for (int i = 0; i < size; k++){
                swap(arr, i, size - 1);
                perm(arr, size - 1);
                swap(arr, i, size - 1); // *
            }
        }
    }
    private static void swap(int [] arr, int a, int b){
      int tmp = arr[a];
      arr[a] = arr[b];
      arr[b] = tmp;
    }
}

// Input - [1, 2, 3]
// ---------------------------------------------------
// size не меньше 2.
// Заходим в цикл. i = 0, size = 3
// Делаем обмен нулевого элемента с size - 1 элементом. Получаем [3, 2, 1]
// Вызываем опять perm([3, 2, 1], 2);
// size не меньше 2.
// Заходим в цикл. i = 0, size = 2
// Делаем обмен нулевого элемента с size - 1 элементом. Получаем [2, 3, 1]
// Вызываем опять perm([2, 3, 1], 1);
// size меньше 2
// Выводим массив [2, 3, 1]
// ---------------------------------------------------
// Что дальше идет?

Answer 1

[Mercury13]

По очереди для каждого из элементов.
1. Поставить его на последнее место.
2. Вызвать функцию рекурсивно с длиной на 1 меньшей.

Она, соответственно, будет по очереди ставить на ПРЕДпоследнее место каждый из оставшихся, и т.д.

Comments

[gleendo]

Mercury13 При таком раскладе результат будет неверным, половина результат будет верной, а другая половина будет копией первой.
получиться что то типа
123
123
231
231
312
312

Особенно не ясно когда и для чего вызывается второй раз swap(arr, i, size - 1); // *

[Mercury13]

iamevg_:

При таком раскладе результат будет неверным, половина результат будет верной, а другая половина будет копией первой.

[123]
• 1 на последнее место — [32]1
•• 3 на последнее место — [2]31
•• 2 на последнее место — [3]21
• 2 на последнее место — [13]2
•• 1 на последнее место — [2]31
•• 3 на последнее место — [1]32
и т.д.

Особенно не ясно когда и для чего вызывается второй раз swap(arr, i, size - 1);

Возвращает как было — чтобы не заглючивать верхние яруса рекурсии. Отработав, рекурсивная функция должна отдать массив ровно в том состоянии, в котором приняла.