Ordenar la permutación de N números naturales usando swaps a la derecha cíclicos triples

Dada una array arr[] de tamaño N que contiene las permutaciones de los N números naturales, la tarea es ordenar las permutaciones de N números naturales con la ayuda de intercambios a la derecha cíclicos triples.

Cambios a la derecha cíclicos triples: se refiere al cambio a la derecha cíclico triple en el que: 

arr[i] -> arr[j] -> arr[k] -> arr[i]

Ejemplos:  

Entrada: arr[] = {3, 2, 4, 1} 
Salida: 1 
1 3 4 
Explicación: 
En la operación 1 se eligen los índices 1, 3 y 4 y se desplazan cíclicamente – 
arr[1] = arr[4 ] = 1 
arr[3] = arr[1] = 3 
arr[4] = arr[3] = 4 
Por lo tanto, el arreglo final será {1, 2, 3, 4}.

Entrada: arr[] = {2, 3, 1} 
Salida: 1 
1 2 3  

Enfoque: la idea es atravesar la array y encontrar los elementos de la array que no están en su posición ordenada real, lo que puede verificarse mediante if  . Porque solo hay N elementos naturales en la array. Finalmente, encuentre las rotaciones cíclicas de longitud impar requeridas en la array para obtener la forma ordenada de la array. Si se requieren rotaciones cíclicas de longitud uniforme, entonces no es posible ordenar los elementos de la array.

A continuación se muestra la implementación del enfoque anterior:  

// C++ implementation to find the
// number of operations required to
// sort the elements of the array
 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
// Function to sort the permutation
// with the given operations
void sortPermutation(ll arr[], ll n)
{
    vector<pair<ll,
                pair<ll, ll> > >
        ans;
    vector<ll> p;
 
    // Visited array to check the
    // array element is at correct
    // position or not
    bool visited[200005] = { 0 };
 
    // Loop to iterate over the elements
    // of the given array
    for (ll i = 1; i <= n; i++) {
 
        // Condition to check if the
        // elements is at its correct
        // position
        if (arr[i] == i) {
            visited[i] = 1;
            continue;
        }
        else {
 
            // Condition to check if the
            // element is included in any
            // previous cyclic rotations
            if (!visited[i]) {
                ll x = i;
                vector<ll> v;
 
                // Loop to find the cyclic
                // rotations in required
                while (!visited[x]) {
                    visited[x] = 1;
                    v.push_back(x);
                    x = arr[x];
                }
 
                // Condition to check if the
                // cyclic rotation is a
                // valid rotation
                if ((v.size() - 3) % 2 == 0) {
                    for (ll i = 1; i < v.size();
                         i += 2) {
 
                        ans
                            .push_back(
                                make_pair(
                                    v[0],
                                    make_pair(
                                        v[i], v[i + 1])));
                    }
                    continue;
                }
                p.push_back(v[0]);
                p.push_back(v[v.size() - 1]);
 
                // Loop to find the index of the
                // cyclic rotation
                // for the current index
                for (ll i = 1; i < v.size() - 1;
                     i += 2) {
                    ans
                        .push_back(
                            make_pair(
                                v[0],
                                make_pair(
                                    v[i], v[i + 1])));
                }
            }
        }
    }
 
    // Condition to if the cyclic
    // rotation is a valid rotation
    if (p.size() % 4) {
        cout << -1 << "\n";
        return;
    }
 
    // Loop to find all the valid operations
    // required to sort the permutation
    for (ll i = 0; i < p.size(); i += 4) {
        ans.push_back(
            make_pair(p[i],
                      make_pair(p[i + 1], p[i + 2])));
        ans.push_back(
            make_pair(p[i + 2],
                      make_pair(p[i], p[i + 3])));
    }
 
    // Total operation required
    cout << ans.size() << "\n";
    for (ll i = 0; i < ans.size(); i++) {
        cout << ans[i].first << " "
             << ans[i].second.first << " "
             << ans[i].second.second << "\n";
    }
}
 
// Driver Code
int main()
{
    ll arr[] = { 0, 3, 2, 4, 1 };
    ll n = 4;
 
    // Function Call
    sortPermutation(arr, n);
    return 0;
}

# Python3 implementation to find the
# number of operations required to
# sort the elements of the array
 
# Function to sort the permutation
# with the given operations
def sortPermutation(arr, n):
 
    ans = []
    p = []
 
    # Visited array to check the
    # array element is at correct
    # position or not
    visited = [0] * 200005
 
    # Loop to iterate over the elements
    # of the given array
    for i in range(1, n + 1):
 
        # Condition to check if the
        # elements is at its correct
        # position
        if (arr[i] == i):
            visited[i] = 1
            continue
 
        else:
 
            # Condition to check if the
            # element is included in any
            # previous cyclic rotations
            if (visited[i]==False):
                x = i
                v = []
 
                # Loop to find the cyclic
                # rotations in required
                while (visited[x] == False):
                    visited[x] = 1
                    v.append(x)
                    x = arr[x]
 
                # Condition to check if the
                # cyclic rotation is a
                # valid rotation
                if ((len(v) - 3) % 2 == 0):
                    for i in range(1, len(v), 2):
                        ans.append([v[0], v[i], v[i + 1]])
                    continue
 
                p.append(v[0])
                p.append(v[len(v) - 1])
 
                # Loop to find the index of the
                # cyclic rotation
                # for the current index
                for i in range(1, len(v) - 1, 2):
                    ans.append([v[0], v[i], v[i + 1]])
 
    # Condition to if the cyclic
    # rotation is a valid rotation
    if (len(p) % 4):
        print(-1)
        return
 
    # Loop to find athe valid operations
    # required to sort the permutation
    for i in range(0, len(p), 4):
        ans.append([p[i], p[i + 1], p[i + 2]])
        ans.append(p[i [+ 2], p[i], p[i + 3]])
 
    # Total operation required
    print(len(ans))
    for i in ans:
        print(i[0], i[1], i[2])
 
# Driver Code
if __name__ == '__main__':
    arr=[0, 3, 2, 4, 1]
    n = 4
 
    # Function Call
    sortPermutation(arr, n)
 
# This code is contributed by Mohit Kumar

1
1 3 4