algorithm - partes - permuta codigo civil
Contando los swaps adyacentes necesarios para convertir una permutación en otra (6)
Aquí hay una solución simple y eficiente:
Deje Q[ s2[i] ] = the positions character s2[i] is on in s2 . Deje P[i] = on what position is the character corresponding to s1[i] in the second string .
Para construir Q y P:
for ( int i = 0; i < s1.size(); ++i )
Q[ s2[i] ].push_back(i); // basically, Q is a vector [0 .. 25] of lists
temp[0 .. 25] = {0}
for ( int i = 0; i < s1.size(); ++i )
P[i + 1] = 1 + Q[ s1[i] ][ temp[ s1[i] ]++ ];
Ejemplo:
1234
s1: abcd
s2: acdb
Q: Q[a = 0] = {0}, Q[b = 1] = {3}, Q[c = 2] = {1}, Q[d = 3] = {2}
P: P[1] = 1, P[2] = 4 (because the b in s1 is on position 4 in s2), P[3] = 2
P[4] = 3
P tiene 2 inversiones ( 4 2 y 4 3 ), así que esta es la respuesta.
Esta solución es O(n log n) porque la construcción de P y Q se puede hacer en O(n) y la ordenación por fusión puede contar inversiones en O(n log n) .
Nos dan dos secuencias de letras minúsculas del alfabeto latino. Ambos tienen la misma longitud y tienen la misma cantidad de tipos de letras (la primera tiene un número igual de t como el segundo y así sucesivamente). Estamos obligados a encontrar la cantidad mínima de swaps ( mediante "swap" queremos decir cambiar el orden de las dos letras vecinas ) necesarios para transformar la primera secuencia en la segunda. Podemos suponer con seguridad que cada dos secuencias PUEDEN transformarse entre sí. Podríamos hacer esto con la fuerza bruta, pero las secuencias son demasiado largas para eso.
Entrada:
La longitud de las secuencias (al menos 2, como máximo 999999) y luego dos secuencias.Salida:
Un número entero que representa la cantidad de intercambios necesarios para que las secuencias sean iguales.Ejemplo:
{5, aaaaa, aaaaa} debería dar salida a {0},
{4, abcd, acdb} debería generar {2}.
Lo primero que se me vino a la mente fue bubblesort. Podemos simplemente burbujear la secuencia contando cada intercambio. El problema es: a) es O (n ^ 2) el peor de los casos b) No estoy convencido de que me daría el número más pequeño para cada caso ... Incluso el bubblesort optimizado no parece estar haciendo el truco. Podríamos implementar el tipo de cóctel que resolvería el problema con las tortugas, pero ¿me dará el mejor rendimiento? ¿O tal vez hay algo más simple / más rápido?
Esta pregunta también se puede expresar como: ¿Cómo podemos determinar la distancia de edición entre dos cadenas cuando la única operación permitida es la transposición?
En cuanto al número mínimo de permutas (necesariamente no adyacentes) necesarias para convertir una permutación en otra, la métrica que debe usar es la distancia de Cayley, que es esencialmente el tamaño de la permutación: la cantidad de ciclos.
Contar el número de ciclos en una permutación es un asunto bastante trivial. Un simple ejemplo. Supongamos permutación 521634.
Si marca la primera posición, tiene 5, en la 5ª tiene 3 y en la 3ª tiene 1, cerrando el primer ciclo. 2 está en la 2ª posición, por lo que hace un ciclo en sí mismo y 4 y 6 hacen el último ciclo (4 está en la 6ª posición y 6 en la 4ª). Si desea convertir esta permutación en la permutación de identidad (con el número mínimo de intercambios), debe reordenar cada ciclo de forma independiente. El número total de intercambios es la longitud de la permutación (6) menos el número de ciclos (3).
Dadas dos permutaciones, la distancia entre ellas es equivalente a la distancia entre la composition de la primera con la inversa de la segunda y la identidad (calculada como se explicó anteriormente). Por lo tanto, lo único que debe hacer es componer la primera permutación y la inversa de la segunda y contar el número de ciclos en el resultado. Todas estas operaciones son O (n), por lo que puede obtener el número mínimo de intercambios en tiempo lineal.
He escrito una Permutation clase que, entre otras cosas, puede devolver una cantidad de transposiciones necesarias para convertir una permutación dada en identidad. Esto se hace creando órbitas (ciclos) y contando sus longitudes. La terminología está tomada de Kostrikin A., I., "Introduction to Linear Algebra I" .
Incluye:
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>
Permutación de clase:
class Permutation {
public:
struct ei_element { /* element of the orbit*/
int e; /* identity index */
int i; /* actual permutation index */
};
typedef std::vector<ei_element> Orbit; /* a cycle */
Permutation( std::vector<int> const& i_vector);
/* permute i element, vector is 0 indexed */
int pi( int i) const { return iv[ i - 1]; }
int i( int k) const { return pi( k); } /* i_k = pi(k) */
int q() const { /* TODO: return rank = q such that pi^q = e */ return 0; }
int n() const { return n_; }
/* return the sequence 1, 2, ..., n */
std::vector<int> const& Omega() const { return ev; }
/* return vector of cycles */
std::vector<Orbit> const& orbits() const { return orbits_; }
int l( int k) const { return orbits_[ k].size(); } /* length of k-th cycle */
int transpositionsCount() const; /* return sum of all transpositions */
void make_orbits();
private:
struct Increment {
int current;
Increment(int start) : current(start) {}
int operator() () {
return current++;
}
};
int n_;
std::vector<int> iv; /* actual permutation */
std::vector<int> ev; /* identity permutation */
std::vector<Orbit> orbits_;
};
Definiciones:
Permutation::Permutation( std::vector<int> const& i_vector) :
n_( i_vector.size()),
iv( i_vector), ev( n_) {
if ( n_) { /* fill identity vector 1, 2, ..., n */
Increment g ( 1);
std::generate( ev.begin(), ev.end(), g);
}
}
/* create orbits (cycles) */
void Permutation::make_orbits() {
std::set<int> to_visit( ev.begin(), ev.end()); // identity elements to visit
while ( !to_visit.empty()) {
/* new cycle */
Orbit orbit;
int first_to_visit_e = *to_visit.begin();
to_visit.erase( first_to_visit_e);
int k = first_to_visit_e; // element in identity vector
/* first orbit element */
ei_element element;
element.e = first_to_visit_e;
element.i = i( first_to_visit_e);
orbit.push_back( element);
/* traverse permutation until cycle is closed */
while ( pi( k) != first_to_visit_e && !to_visit.empty()) {
k = pi( k);
ei_element element;
element.e = k;
element.i = pi( k);
orbit.push_back( element);
to_visit.erase( k);
}
orbits_.push_back( orbit);
}
}
y:
/* return sum of all transpositions */
int Permutation::transpositionsCount() const {
int count = 0;
int k = 0;
while ( k < orbits_.size()) {
count += l( k++) - 1; /* sum += l_k - 1 */
}
return count;
}
uso:
/*
*
*/
int main(int argc, char** argv) {
//1, 2, 3, 4, 5, 6, 7, 8 identity (e)
int permutation[] = {2, 3, 4, 5, 1, 7, 6, 8}; // actual (i)
std::vector<int> vp( permutation, permutation + 8);
Permutation p( vp);
p.make_orbits();
int k = p.orbits().size();
std::cout << "Number of cycles:" << k << std::endl;
for ( int i = 0; i < k; ++i) {
std::vector<Permutation::ei_element> v = p.orbits()[ i];
for ( int j = 0; j < v.size(); ++j) {
std::cout << v[ j].e << "," << v[ j].i << " | ";
}
std::cout << std::endl;
}
std::cout << "Steps needed to create identity permutation: "
<< p.transpositionsCount();
return 0;
}
salida:
Cantidad de ciclos: 3
1,2 | 2,3 | 3,4 | 4,5 | 5,1 |
6,7 | 7,6 |
8,8 |
Pasos necesarios para crear la permutación de identidad: 5
EJECUTADO CON ÉXITO (tiempo total: 82 ms)
La conversión de la permutación de uno a otro se puede convertir en un problema similar ( número de intercambios en una permutación ) invirtiendo la permutación objetivo en O (n), componiendo las permutaciones en O (n) y luego encontrando el número de permutas desde allí a una permutación de identidad. Dado:
int P1[] = {0, 1, 2, 3}; // abcd
int P2[] = {0, 2, 3, 1}; // acdb
// we can follow a simple algebraic modification
// (see http://en.wikipedia.org/wiki/Permutation#Product_and_inverse):
// P1 * P = P2 | premultiply P1^-1 *
// P1^-1 * P1 * P = P1^-1 * P2
// I * P = P1^-1 * P2
// P = P1^-1 * P2
// where P is a permutation that makes P1 into P2.
// also, the number of steps from P to identity equals
// the number of steps from P1 to P2.
int P1_inv[4];
for(int i = 0; i < 4; ++ i)
P1_inv[P1[i]] = i;
// invert the first permutation O(n)
int P[4];
for(int i = 0; i < 4; ++ i)
P[i] = P2[P1_inv[i]];
// chain the permutations
int num_steps = NumSteps(P, 4); // will return 2
// now we just need to count the steps
Para contar los pasos, se puede diseñar un algoritmo simple, como:
int NumSteps(int *P, int n)
{
int count = 0;
for(int i = 0; i < n; ++ i) {
for(; P[i] != i; ++ count) // could be permuted multiple times
swap(P[P[i]], P[i]); // look where the number at hand should be
}
// count number of permutations
return count;
}
Esto siempre intercambia un elemento por un lugar donde debería estar en la permutación de identidad, por lo tanto, en cada paso deshace y cuenta un intercambio. Ahora, siempre que el número de intercambios que devuelve sea realmente mínimo, el tiempo de ejecución del algoritmo está limitado por él y se garantiza que finalizará (en lugar de quedar atrapado en un ciclo infinito). Se ejecutará en O(m) swaps o O(m + n) iteraciones de bucle donde m es el número de swaps (el count devuelto) y n es el número de elementos en la secuencia ( 4 ). Tenga en cuenta que m < n siempre es verdadero. Por lo tanto, esto debería ser superior a las soluciones O(n log n) , ya que el límite superior es O(n - 1) de swaps u O(n + n - 1) de iteraciones de bucle aquí, que es prácticamente O(n) (factor constante de 2 omitido en este último caso).
El algoritmo solo funcionará para permutaciones válidas, se repetirá infinitamente para secuencias con valores duplicados y hará acceso de matriz fuera de límites (y bloqueo) para secuencias con valores distintos de [0, n) . here puede encontrar un caso de prueba completo (compilaciones con Visual Studio 2008, el algoritmo en sí mismo debería ser bastante portátil). Genera todas las permutaciones posibles de longitudes 1 a 32 y las comprobaciones frente a soluciones, generadas con la primera búsqueda de ancho (BFS), parece funcionar para todas las permutaciones de longitudes 1 a 12, luego se vuelve bastante lento, pero supongo que continuará funcionando .
Lo que está buscando puede ser idéntico a la " distancia de Kendall tau ", que es la diferencia (normalizada) de pares concordantes menos discordantes. Ver Wikipedia , donde se dice que es equivalente a la distancia de ordenación de burbuja.
En R, las funciones están disponibles no solo para computar tau, por ej.
cor( X, method="kendall", use="pairwise" ) ,
sino también para probar el significado de la diferencia, por ejemplo
cor.test( x1, x2, method="kendall" ) ,
e incluso pueden tener en cuenta adecuadamente los vínculos.
El algoritmo " distancia de Kendall tau " es la solución exacta en este caso, donde se debe encontrar el número de intercambios de elementos adyacentes .
Ejemplo.
eyssaasse ( cadena de base )
seasysaes
La cadena base proporciona índices para cada elemento: e = 0, y = 1, s = 2, s = 3, a = 4, a = 5, s = 6, s = 7, e = 8;
Algunos elementos son duplicados, entonces:
1) Crea un diccionario donde los elementos son claves, y los valores son listas de índices:
idx = {'' e '' => [0, 8], '' y '' => [1], '' s '' => [2, 3, 6, 7], '' a '' => [4, 5]}
2) Cree un mapa de índice de la segunda cadena usando índices de elemento en el diccionario idx :
seasysaes -> 204316587 (bucle ''seasysaes'' y pop el siguiente índice de las listas para cada clave en idx )
3) Cree una lista de todas las combinaciones emparejadas de este mapa, 204316587: 20 24 23 21 26 25 28 27 04 03 01 06 ... 65 68 67 58 57 87;
Pasa por estos pares contando aquellos donde el primer número es más grande que el segundo número.
Este recuento es el número buscado de swaps adyacentes entre cadenas .
Script de Python:
from itertools import combinations, cycle
word = ''eyssaasse'' # base string
cmpr = ''seasysaes'' # a string to find number of swaps from the base string
swaps = 0
# 1)
chars = {c: [] for c in word}
[chars[c].append(i) for i, c in enumerate(word)]
for k in chars.keys():
chars[k] = cycle(chars[k])
# 2)
idxs = [next(chars[c]) for c in cmpr]
# 3)
for cmb in combinations(idxs, 2):
if cmb[0] > cmb[1]:
swaps += 1
print(swaps)
El número de intercambios entre ''eyssaasse'' y ''seasysaes'' es 7.
Para ''reviver'' y ''vrerevi'' es 8.