How to permute array elements by shifting and then undoing?

Question

#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);
}

I know the swap method of code for permutating elements. I am trying to implement this method in which I am printing every element as I get it and then shift all the elements after that by one place below.

But because of it, the whole array itself changes.

How do I get my previous array back when I complete one iteration, just as we get the array by unswapping the swapped elements.

Answer 1

There is no need to undoing here, you just need to rotate array:

#include <iostream>
using namespace std;

void permute(int arr[], int len, int total_len) {

    if (len > 1) {

        for (int i = 0; i < len; i++) {

            permute(arr, len - 1, total_len);

            // <<<
            int buff = arr[0];
            for (int j = 0; j < len - 1; j++) {
                arr[j] = arr[j + 1];
            }
            arr[len - 1] = buff;
            // >>> - It can be simplified:
            //std::rotate(arr, arr + 1, arr + len);
        }
    }
    else {
        for (int j = 0; j < total_len; j++)
            cout << arr[j] << " ";
        cout << endl;
    }
}

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

The same thing, but using std::array class and without passing the total_len:

#include <iostream>
#include <array>
using namespace std;

template <typename T, size_t N>
void permute(array<T, N> arr, size_t len) {

    if (len > 1) {
        auto rem_len = len - 1;
        auto first = arr.begin();
        auto mid = first + 1;
        auto last = first + len;
        while (len--) {
            permute(arr, rem_len);
            rotate(first, mid, last);
        }
    }
    else {
        for (const auto& a : arr)
            cout << a << ' ';
        cout << endl;
    }
}

int main() {
    const size_t n = 3;
    array<int, n> arr;
    for (auto& a : arr) cin >> a;
    permute(arr, n);
}