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++
// 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
# 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