Почему некорректно выводит перестановки методом поиска с возвратом?

Question

[Perflex_er]

#include <iostream>
using namespace std;
void perm( int *arr, int size, int index = 0 )
{
    int i;
    if( index == size )
    {
        for( i = 0; i < size; i++ )
        cout << arr[i] << " ";
        cout << endl;
        return;
    }
    perm( arr, size, index + 1 );
    for( i = index + 1; i < size; i++ )
    {
        swap( arr[i], arr[index] );
        perm( arr, size, index + 1 );
        swap( arr[i], arr[index] );
    }
    return;
}
int main()
{
    int ar[] = { 1, 2, 3, 4 };
    perm( ar, 4 );
    return 0;
}

Дано множество и нужно методом поиска с возвратом вывести все возможные перестановки множества. Проблема в том, что казалось бы код работает, но на 5 И 6 19 и 20 25 и 26 выводит неправильно должно быть 1 4 2 3 и 1 4 3 2 ,а не 1 4 3 2 и 1 4 2 3(поменяны местами),но на этом сложности не заканчиваются. При записи неправильных рядков я пропустил 11 и 12,ведь там все работает правильно
Объясните пожалуйста, почему так происходит?

Answer 1

[Wataru]

А вы можете сами логику своего решения сформулировать? Какой инвариант поддерживается при запуске рекурсивной функции?

Похоже, что первые 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;

Comments

[Perflex_er]

Спасибо Вам огромное, увидел только сейчас, но мне очень пригодилось