А вы можете сами логику своего решения сформулировать? Какой инвариант поддерживается при запуске рекурсивной функции?
Похоже, что первые index позиций в массиве arr считаются зафиксированными.
Тогда вам надо ставить на следующее место все оставшиеся числа по порядку и рекурсивно запускаться дальше.
Но ваш подход со swap-ами первого не зафиксированного числа со всеми остальными перемешивает эти оставшиеся числа. Если вы пройдетесь по вашему решению отладчиком или будете выводить arr в начале функции всегда, то вы заметите, что там числа после index идут не по порядку. И ваш алгоритм, беря их индесы по порядку, может сначала поробовать не самое маленькое число.
Вам надо добиться того, что оставшиеся в arr числа после index всегда шли по порядку на момент рекурсивного вызова.
Пусть ставшиеся числа 1,2,3,4. Сначала вы ставите на первую позицию 1 (оставляете все как есть).
Потом вы должны получить в массиве 2,1,3,4 и запуститься рекурсивно. Это один swap.
Потом надо получить в массиве 3,1,2,4. Это можно сделать одним swap из предыдущего состояния.
Важно тут, что вы не возвращаете массив назад после каждого рекурсивного вызова. Иначе вам пришлось бы делать циклический сдвиг части массива на каждой итерации (1,2,3,4 -> 3,1,2,4).
В конце, после последнего рекурсивного вызова у вас будет 4,1,2,3. Чтобы вернуть все как было вам придется после цикла с рекурсивными вызовами сделать циклический сдвиг массива влево на 1 позицию.
Т.е. рекурсивные вызовы будут как-то так:
perm( arr, size, index + 1 );
for( i = index + 1; i < size; i++ )
{
swap( arr[i], arr[index] );
perm( arr, size, index + 1 );
}
int tmp = arr[index];
for (i = index; i < size-1; i++)
arr[i] = arr[i+1];
arr[size-1] = tmp;
