Dada una string que consta de los primeros N alfabetos distintos, la tarea es ordenar la string usando como máximo N/2 movimientos. Cada movimiento implica lo siguiente:
- Seleccione cualquiera de los 3 índices distintos.
- Realice un cambio cíclico en los alfabetos en estos índices.
Si es posible ordenar las strings, imprima el recuento de movimientos requeridos. De lo contrario, imprima «No es posible» .
Ejemplos:
Entrada: str = “cbda”
Salida:
posible
1
Explicación:
Seleccionando los índices 0, 2 y 3 y realizando un solo desplazamiento circular entre ellos, la string dada “cbda” se convierte en “abcd”.Entrada: str = “cba”
Salida: No es posible
Enfoque:
Para resolver el problema, siga los pasos a continuación:
- Almacene los números enteros que denotan la corrección de los caracteres de la string en un vector .
- Coloque correctamente aquellos elementos que puedan ocupar índices correctos en un solo ciclo.
- Recorrer un elemento del vector
- Si el elemento no está en su posición de índice ordenado, compruebe si se pueden colocar dos o más números en los índices correctos en un ciclo. Si se cumple la condición, realice el ciclo; de lo contrario, verifique si hay un índice distinto que no contenga el elemento correcto disponible. Si se cumple la condición, seleccione este índice como el tercer índice del ciclo y realice el ciclo. Si no se cumple ninguna de las condiciones anteriores, la clasificación sería imposible. Por lo tanto, salga del bucle e imprima «No es posible».
- Una vez que se realiza un cambio cíclico, almacene los índices involucrados en el cambio.
- Si el elemento está en su posición ordenada, muévase al siguiente índice.
- Repita los dos pasos anteriores para todos los elementos vectoriales.
- Después de completar el recorrido, si todo el arreglo está ordenado, imprima los turnos requeridos. De lo contrario, escriba «No es posible».
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for sorting a
// string using cyclic shift
// of three indices
#include <bits/stdc++.h>
using namespace std;
void sortString(vector<int>& arr, int n,
int moves)
{
// Store the indices
// which haven't attained
// its correct position
vector<int> pos;
// Store the indices
// undergoing cyclic shifts
vector<vector<int> > indices;
bool flag = false;
for (int i = 0; i < n; i++) {
// If the element is not at
// it's correct position
if (arr[i] != i) {
// Check if all 3 indices can be
// placed to respective correct
// indices in a single move
if (arr[arr[arr[i]]] == i
&& arr[arr[i]] != i) {
int temp = arr[arr[i]];
indices.push_back({ i, arr[i],
arr[arr[i]] });
swap(arr[i], arr[arr[i]]);
swap(arr[i], arr[temp]);
}
}
// If the i-th index is still
// not present in its correct
// position, store the index
if (arr[i] != i) {
pos.push_back(i);
}
}
for (int i = 0; i < n; i++) {
if (arr[i] != i) {
int pos1 = i, pos2 = arr[i];
int pos3 = arr[arr[i]];
// To check if swapping two indices
// places them in their correct
// position
if (pos3 != pos1) {
indices.push_back({ pos1,
pos2,
pos3 });
swap(arr[pos1], arr[pos2]);
swap(arr[pos1], arr[pos3]);
pos.erase(find(
pos.begin(),
pos.end(), pos2));
pos.erase(find(
pos.begin(),
pos.end(), pos3));
if (arr[pos1] == pos1) {
pos.erase(find(
pos.begin(),
pos.end(),
pos1));
}
}
else {
if (pos3
== *pos.begin()) {
if (*pos.begin()
!= pos.back()) {
auto it
= ++pos.begin();
pos3 = *(it);
if (*it != pos.back()
&& pos3 == pos2) {
pos3 = *(++it);
}
else if (*it == pos.back()
&& pos3 == pos2) {
flag = true;
break;
}
}
else {
flag = true;
break;
}
}
indices.push_back({ pos1, pos2,
pos3 });
swap(arr[pos1], arr[pos2]);
swap(arr[pos1], arr[pos3]);
pos.erase(find(
pos.begin(),
pos.end(),
pos2));
}
}
if (arr[i] != i) {
i--;
}
}
if (flag == true
|| indices.size() > moves) {
cout << "Not Possible" << endl;
}
else {
cout << indices.size() << endl;
// Inorder to see the indices that
// were swapped in rotations,
// uncomment the below code
/*
for (int i = 0; i < indices.size();
i++) {
cout << indices[i][0] << " "
<< indices[i][1] << " "
<< indices[i][2] << endl;
}
*/
}
}
// Driver Code
int main()
{
string s = "adceb";
vector<int> arr;
for (int i = 0; i < s.size(); i++) {
arr.push_back(s[i] - 'a');
}
sortString(arr, s.size(),
floor(s.size() / 2));
}
Python3
# Python3 program for sorting a
# string using cyclic shift
# of three indices
import math
def sortString(arr, n, moves):
# Store the indices
# which haven't attained
# its correct position
pos = []
# Store the indices
# undergoing cyclic shifts
indices = []
flag = False
for i in range(n):
# If the element is not at
# it's correct position
if (arr[i] != i):
# Check if all 3 indices can be
# placed to respective correct
# indices in a single move
if (arr[arr[arr[i]]] == i and
arr[arr[i]] != i):
temp = arr[arr[i]]
indices.append([i, arr[i],
arr[arr[i]]])
sw = arr[i]
arr[i] = arr[arr[i]]
arr[sw] = sw
sw = arr[i]
arr[i] = arr[temp]
arr[temp] = sw
# If the i-th index is still
# not present in its correct
# position, store the index
if (arr[i] != i):
pos.append(i)
for i in range(n):
if (arr[i] != i):
pos1 = i
pos2 = arr[i]
pos3 = arr[arr[i]]
# To check if swapping two indices
# places them in their correct
# position
if (pos3 != pos1):
indices.append([pos1, pos2, pos3])
arr[pos1], arr[pos2] = arr[pos2], arr[pos1]
arr[pos1], arr[pos3] = arr[pos3], arr[pos1]
pos.remove(pos2)
if pos3 in pos:
pos.remove(pos3)
if (arr[pos1] == pos1):
pos.remove(pos1)
else:
if (pos3 == pos[0]):
it = 0
if (pos[0] != pos[-1]):
it = it + 1
pos3 = pos[it]
if (pos[it] != pos[-1] and
pos3 == pos2):
it = it + 1
pos3 = pos[it]
elif (pos[it] == pos[-1] and
pos3 == pos2):
flag = True
break
else:
flag = True
break
indices.append([pos1, pos2, pos3])
arr[pos1], arr[pos2] = arr[pos2], arr[pos1]
arr[pos1], arr[pos3] = arr[pos3], arr[pos1]
pos.remove(pos2)
if (arr[i] != i):
i = i - 1
if (flag == True or len(indices) > moves):
print("Not Possible")
else:
# Inorder to see the indices that
# were swapped in rotations,
# uncomment the below code
# for i in range len(indices):
# print (indices[i][0],
# indices[i][1], indices[i][2])
print(len(indices))
# Driver code
s = "adceb"
arr = []
for i in s:
arr.append(ord(i) - ord('a'))
sortString(arr, len(s), math.floor(len(s) / 2))
# This code is contributed by costheta_z
Producción:
1
Publicación traducida automáticamente
Artículo escrito por costheta_z y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA