Как переставить элементы массива, сдвигая их, а затем отменяя?

На чтение 3 мин Опубликовано 08.10.2024

Содержание

Вопрос или проблема
Ответ или решение
Объяснение кода:

Вопрос или проблема

#include <iostream>
using namespace std;

void permute(int arr[],int len){
    //if(len==1) cout << arr[fixed];
    for(int i=0; i<len; i++){
        cout << arr[i] << " ";
        if(len==0) return;
        for(int j=i; j<len-1; j++){
            arr[j] = arr[j+1];
        }
        permute(arr, len-1);
        cout << endl;
    }
}

int main(){
    int n = 3;
    int arr[n];
    for(int i=0; i<n; i++) cin >> arr[i];
    permute(arr, n);
}

Я знаю метод обмена для перестановки элементов. Я пытаюсь реализовать этот метод, при котором я печатаю каждый элемент по мере его получения, а затем смещаю все последующие элементы на одну позицию ниже.

Но из-за этого весь массив изменяется.

Как я могу вернуть мой предыдущий массив после завершения одной итерации, так же, как мы получаем массив, отменяя обмененные элементы.

Ответ или решение

Чтобы разрешить вашу задачу с перестановкой элементов массива путем сдвига и последующего восстановления исходного состояния массива, необходимо использовать подход, который позволит вам сохранять состояние массива до начала перестановки и восстанавливать его после выполнения рекурсивного вызова.

Вот переработанный вариант вашего кода:

#include <iostream>
using namespace std;

void permute(int arr[], int len) {
    // Если длина массива нулевая, просто возвращаемся
    if (len == 0) return;

    // Шаг 1: Перебираем элементы массива
    for (int i = 0; i < len; i++) {
        // Печатаем текущий элемент
        cout << arr[i] << " ";

        // Шаг 2: Сохраняем состояние массива, чтобы восстановить его позже
        int temp = arr[i];

        // Шаг 3: Сдвигаем элементы массива влево
        for (int j = i; j < len - 1; j++) {
            arr[j] = arr[j + 1];
        }

        // Шаг 4: Рекурсивно вызываем функцию для остальной части массива
        permute(arr, len - 1);

        // Шаг 5: Восстанавливаем исходное состояние массива
        for (int j = len - 1; j > i; j--) {
            arr[j] = arr[j - 1];
        }
        arr[i] = temp;

        cout << endl; // Для изменения строки после каждой перестановки
    }
}

int main() {
    int n = 3;
    int arr[n];

    // Ввод элементов массива
    cout << "Введите " << n << " элемента(ов): ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // Вызов функции перестановки
    cout << "Перестановки массива: " << endl;
    permute(arr, n);

    return 0;
}

Объяснение кода:

Рекурсия: Функция permute принимает массив и его длину. Если длина равна нулю, мы просто выходим из функции.
Перебор элементов: Внешний цикл проходит по всем элементам массива. Для каждого элемента:
- Печатаем текущий элемент.
- Сохраняем его значение во временной переменной для последующего восстановления.
- Сдвигаем оставшиеся элементы влево.
Рекурсивный вызов: Производим рекурсивный вызов для уменьшенной длины массива (len – 1).
Восстановление массива: После завершения вызова рекурсии, выполняем обратный процесс: восстанавливаем исходное состояние массива, воссоздавая элементы, которые были сдвинуты.
Ввод и вывод: В main осуществляется ввод элементов массива и вывод перестановок.

Таким образом, с помощью предложенных изменений, вы можете безопасно выполнять перестановку элементов с использованием метода сдвига и восстановления их состояния.