[color=#999999]Esta actividad pertenece al [i]libro de GeoGebra[/i] [url=https://www.geogebra.org/m/qg2gkkat]Música y Matemáticas[/url].[/color][br][br][b]La distancia de permutación [/b][br] [br]Aquí llamaremos [i]permutación[/i] al intercambio de dos elementos [i]adyacentes[/i], es decir, al intercambio de un ‘uno’ y un ‘cero’ que son adyacentes en una cadena binaria.[br] [br]La [i]distancia de permutación[/i] entre dos patrones rítmicos se define como el mínimo número de permutaciones que se necesitan para convertir un patrón rítmico en otro. Por ejemplo, el patrón X = [101011010101] puede convertirse en el patrón Y = [101101101010] con un mínimo de cuatro permutaciones, a saber, intercambiando la tercera, la quinta, la sexta y la séptima posición con los correspondientes silencios que van detrás de ellos. [br] [br]Desde el punto de vista musical es razonable usar esta distancia. El oído humano considera como próximos dos patrones rítmicos si el número de cambios entre acentos es pequeño y si tales cambios ocurren entre acentos adyacentes. Además, es interesante observar que el compás bulería resulta precisamente de la permutación de un uno y un cero en el compás soleá. Un ejemplo de esta distancia aplicada a patrones rítmicos del flamenco se ilustra en la siguiente figura, que muestra una distancia de permutación entre la seguiriya y el fandango igual a 4. Ciertos autores sugieren que ésa es la evolución natural entre ambos patrones rítmicos.

[b]Computación eficiente de la distancia de permutación[/b][br][br]Claramente, la distancia de permutación puede obtenerse calculándose todas las permutaciones posibles. Sin embargo, este método básico sería muy costoso para vectores n-dimensionales si n es un valor grande. [br] [br]Un algoritmo mucho más eficiente puede obtenerse si comparamos las distancias de las notas al origen. Lo describimos aquí brevemente. Primero hacemos un barrido de la sucesión binaria y almacenamos un vector con la información del lugar que ocupa cada acento. [br] [br]Por ejemplo, si consideramos:[br][br] X = [ 1 0 1 0 1 1 0 1 0 1 0 1 ][br] Y = [ 1 0 1 1 0 1 1 0 1 0 1 0 ][br][br]entonces almacenamos:[br] [br] U = (u[sub]1[/sub], u[sub]2[/sub],..., u[sub]7[/sub]) = (1, 3, 5, 6, 8, 10, 12) para X y[br] V = (v[sub]1[/sub], v[sub]2[/sub],..., v[sub]7[/sub]) = (1, 3, 4, 6, 7, 9, 11) para Y, respectivamente. [br] [br]De esta forma, la diferencia entre u[sub]i[/sub] y v[sub]i[/sub] es el número mínimo de permutaciones que tienen que realizarse para alinear ambos acentos. [br] [br]Por tanto, en general, la distancia de permutación entre dos conjuntos de U y V con k notas está dado por:

Calcular U y V a partir de X e Y se puede hacer en tiempo lineal con un simple barrido. Por tanto, en tiempo O(n) podemos calcular d[sub]P[/sub](U, V), lo cual da como consecuencia una gran ganancia sobre el uso del algoritmo básico que considera todas las posibles permutaciones. [br] [br]El lector se debe estar preguntando a qué viene toda esta discusión sobre la reducción de la complejidad de O(n[sup]2[/sup]) a O(n) cuando en el caso de los ritmos flamencos tenemos n = 12 y la cota cuadrática es computacionalmente aceptable. La razón es que la diferencia de la complejidad resulta crucial cuando estas distancias se pretenden usar en aplicaciones de recuperación de la información musical, donde hay que extraer piezas enteras de una base de datos en la que n puede ser muy grande.