#include<bits/stdc++.h> #define ll int #define pb push_back #define mp make_pair #define ss second #define ff first using namespace std; bool check(const vector<ll>&data){ for (ll i=0;i<(ll)data.size()-1;i++){ if (data[i]!=(i+1)){ return false; } } return true; } struct node{ vector<ll>data; vector<int>path; }; map<vector<int> ,bool>mm; int main(){ ll n; cin >> n; // Enter n vector<ll>data; for (ll i=n;i>0;i--){ data.pb(i); } queue<node>q; node no; no.data = data; q.push(no); while (q.size() > 0){ no = q.front(); q.pop(); if(mm[no.data]==1) continue; mm[no.data]=1; if (check(no.data)){ //checks whether data is sorted or not cout << "Array is Sorted" << endl; for (ll i=0;i<(ll)no.data.size();i++){ cout << no.data[i] << " "; } cout << endl; cout<<no.path.size()<<endl; cout << "Opertions are:" <<'\n'; for (ll i=0;i<(ll)no.path.size();i++){ if(no.path[i]==0) cout<<"Transpositions (1,2) is performed"<<endl; else if(no.path[i]==1) cout<<"Left Rotate is performed"<<endl; else cout<<"Right Rotate is performed"<<endl; } cout << endl; break; } node n1,n2; n1 = no; n2=no; if(n1.path.size()==0){ swap(n1.data[0],n1.data[1]); //Exchange operation is performed on leftmost two elements n1.path.pb(0); q.push(n1); } else if(*(n1.path.end()-1)!=0){ swap(n1.data[0],n1.data[1]); //Exchange operation is performed on leftmost two elements n1.path.pb(0); q.push(n1); } rotate(no.data.begin(),no.data.begin()+1,no.data.end()); //Left Rotate operation is performed no.path.pb(1); q.push(no); rotate(n2.data.begin(), n2.data.begin()+n2.data.size()-1,n2.data.end()); //Right Rotate operation is performed n2.path.pb(2); q.push(n2); } return 0; }