déterminer si le tableau peut être trié en tournant 3 éléments consécutifs du tableau ?

Question

J'ai une permutation d'une séquence de nombres naturels incrémentés à partir de 1 dans un tableau. Comment puis-je déterminer si le tableau peut être trié en utilisant la rotation de 3 éléments consécutifs ?

J'ai implémenté un algorithme dans lequel je compare les indices du tableau avec l'élément à cet indice dans le tableau. S'ils ne sont pas égaux, j'appelle la fonction choose_indices() qui trouve d'abord l'élément à échanger à la bonne position dans le tableau et après l'avoir trouvé, sélectionne les 3 éléments consécutifs incluant le numéro à échanger et les fait tourner. Après avoir effectué n-1 rotations pour un tableau de taille n, le tableau est trié. Cette implémentation renvoie vrai si un tableau peut être trié en utilisant la rotation de 3 éléments consécutifs, mais demande un délai d'attente pour un tableau si le tableau ne peut pas être trié en utilisant cette méthode.

using namespace std;
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
int n;
void rotate(vector<int> &arr,int end,int mid,int start)
{
    int temp=arr[start];
    arr[start]=arr[end];
    arr[end]=arr[mid];
    arr[mid]=temp;
}
void choose_indices(vector<int> &arr,int s,int q)
{
    for(int l=q;l<n;l++)
    {
        if(arr[l]==s)
        {
            if(l-q>=2)
            {
                rotate(arr,l,l-1,l-2);
                break;
            }
            else
            {
                rotate(arr,l+1,l,l-1);
                break;
            }
        }
    }
}
int main()
{
    vector<int> arr;
    int q,count=0;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>n;
        count=0;
        for(int i=0,p;i<n;i++)
        {
            cin>>p;
            arr.push_back(p);
        }
        for(int j=0,k=1;j<n && k<n; )
        {
            if(arr[j]!=k)
            {
                choose_indices(arr,k,j);
                if(arr[j]==k)
                {
                    j++;
                    k++;
                    count++;
                }
            }
            else
            {
                j++;
                k++;
                count++;
            }
        }
        if(count==n-1)
        {
            cout<<"YES"<<endl;
        }
        else
        {
           cout<<"NO"<<endl;
        }
        arr.clear();
    }
}

Entrée de l'échantillon : 1 2 3 5 4

Pour cette entrée, mon code donne une erreur d'exécution. Comment puis-je savoir si le tableau donné ne peut pas être trié en utilisant la rotation de 3 éléments consécutifs ?

Answer 1

Faire tourner 3 éléments adjacents sera toujours annuler 2 inversions si elles sont présentes ou introduire 2 inversions .

Considérez ceci :

1 2 3 5 4

N'a que 1 inversion Peu importe le nombre de rotations, vous ne pourrez jamais annuler cette inversion sans introduire d'autres inversions, telles que vous ferez toujours tourner 3 éléments consécutifs .

Il suffit de compter le nombre d'inversions et si c'est impair, la réponse est NON sinon OUI . Il existe des algorithmes efficaces pour compter le nombre d'inversions (comme le tri par fusion).

Answer 2

using namespace std;
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstring>
int n;
void rotate(vector<int> &arr,int end,int mid,int start)
{
    int temp=arr[start];
    arr[start]=arr[end];
    arr[end]=arr[mid];
    arr[mid]=temp;
}
void choose_indices(vector<int> &arr,int s,int q)
{
    for(int l=q;l<n;l++)
    {
        if(arr[l]==s)
        {
            if(l-q>=2)
            {
                rotate(arr,l,l-1,l-2);
                break;
            }
            else
            {
                rotate(arr,l+1,l,l-1);
                break;
            }
        }
    }
}
int main()
{
    vector<int> arr;
    int q,count=0;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>n;
        count=0;
        for(int i=0,p;i<n;i++)
        {
            cin>>p;
            arr.push_back(p);
        }
        //Counting the number of inversion in the array
        int ctiv=0;
        for(int r=0;r<n;r++)
        {
            for(int s=r+1;s<n;s++)
            {
                if(arr[r]>arr[s] && r<s)
                {
                    ctiv++;
                }
            }
        }
        if(ctiv%2!=0)
        {
            cout<<"NO"<<endl;
        }
        else 
        {
            for(int j=0,k=1;j<n && k<n; )
            {
                if(arr[j]!=k)
                {
                    choose_indices(arr,k,j);
                    if(arr[j]==k)
                    {
                        j++;
                        k++;
                        count++;
                    }
                }
                else
                {
                    j++;
                    k++;
                    count++;
                }
            }
            if(count==n-1)
            {
                cout<<"YES"<<endl;
            }
            arr.clear();
        }
    }
}

Voici l'algorithme que j'ai conçu qui détermine si l'algorithme donné peut être trié et s'il peut l'être, il trie le tableau donné en effectuant les 3 rotations consécutives nécessaires.