Permutación

ImprimirCitar

Versión matemática de un cambio de orden

Cada una de las seis filas es una permutación diferente de tres bolas distintas

En matemáticas, una permutación de un conjunto es, en términos generales, una disposición de sus miembros en una secuencia u orden lineal o, si el conjunto ya está ordenado, una reorganización de sus elementos. La palabra "permutación" también se refiere al acto o proceso de cambiar el orden lineal de un conjunto ordenado.

Las permutaciones difieren de las combinaciones, que son selecciones de algunos miembros de un conjunto sin importar el orden. Por ejemplo, escrito como tuplas, hay seis permutaciones del conjunto {1, 2, 3}, a saber (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2) y (3, 2, 1). Estos son todos los ordenamientos posibles de este conjunto de tres elementos. Los anagramas de palabras cuyas letras son diferentes también son permutaciones: las letras ya están ordenadas en la palabra original, y el anagrama es un reordenamiento de las letras. El estudio de las permutaciones de conjuntos finitos es un tema importante en los campos de la combinatoria y la teoría de grupos.

Las permutaciones se utilizan en casi todas las ramas de las matemáticas y en muchos otros campos de la ciencia. En informática, se utilizan para analizar algoritmos de clasificación; en física cuántica, para describir estados de partículas; y en biología, para describir secuencias de ARN.

El número de permutaciones de $n$ objetos distintos es $n$ factorial, generalmente escrito como $n!$ , lo que significa que producto de todos los enteros positivos menores o iguales a $n$ .

Técnicamente, una permutación de un conjunto $S$ se define como una bijeción de $S$ a sí mismo. Es decir, es una función de $S$ a $S$ para el cual cada elemento ocurre exactamente una vez como un valor de imagen. Esto está relacionado con la reorganización de los elementos $S$ en que cada elemento $s$ es reemplazado por el correspondiente $f () s)$ . Por ejemplo, la permutación (3, 1, 2) mencionada anteriormente se describe por la función $alpha$ definidas

{displaystyle alpha (1)=3,quad alpha (2)=1,quad alpha (3)=2}

La colección de todas las permutaciones de un conjunto forma un grupo llamado el grupo simétrico del conjunto. La operación del grupo es la composición (conformando dos reorganizaciones dadas en sucesión), que resulta en otra reorganización. Como las propiedades de las permutaciones no dependen de la naturaleza de los elementos del conjunto, es a menudo las permutaciones del conjunto ${1, 2, ldots, n}$ que se consideran para estudiar permutaciones.

En combinatoria elemental, las $k$ -permutaciones, o permutaciones parciales, son los arreglos ordenados de $k$ elementos distintos seleccionados de un conjunto. Cuando $k$ es igual al tamaño del conjunto, estas son las permutaciones del conjunto.

En el rompecabezas popular el cubo de Rubik inventado en 1974 por Ernő Rubik, cada vuelta de las caras del rompecabezas crea una permutación de los colores de la superficie.

Historia

Las permutaciones llamadas hexagramas se usaron en China en el I Ching (Pinyin: Yi Jing) ya en el año 1000 a.

Al-Khalil (717–786), un matemático y criptógrafo árabe, escribió el Libro de mensajes criptográficos. Contiene el primer uso de permutaciones y combinaciones, para enumerar todas las palabras árabes posibles con y sin vocales.

La regla para determinar el número de permutaciones de n objetos se conocía en la cultura india alrededor del año 1150 d.C. El Lilavati del matemático indio Bhaskara II contiene un pasaje que se traduce como:

El producto de la multiplicación de la serie aritmética que comienza y aumenta por unidad y continúa hasta el número de lugares, serán las variaciones del número con cifras específicas.

En 1677, Fabian Stedman describió los factoriales al explicar el número de permutaciones de las campanas en el cambio de sonido. Partiendo de dos campanas: "primero, dos hay que admitir que varíe de dos maneras", lo cual ilustra mostrando 1 2 y 2 1. Luego explica que con tres campanas hay "tres por dos cifras a producir de tres" que nuevamente se ilustra. Su explicación consiste en "desechar 3 y quedará 1,2; desecha 2, y quedará 1,3; desechar 1, y 2.3 quedarán". Luego pasa a cuatro campanas y repite el argumento de desechar mostrando que habrá cuatro conjuntos diferentes de tres. Efectivamente, este es un proceso recursivo. Continúa con cinco campanas usando el "desechar" y tabula las 120 combinaciones resultantes. En este punto se da por vencido y comenta:

Ahora la naturaleza de estos métodos es tal, que los cambios en un número comprenden los cambios en todos los números menores,... insomuch that a compleat El peal de los cambios en un número parece ser formado por la unión de los Peales compleatos en todos los números menores en un cuerpo entero;

Stedman amplía la consideración de las permutaciones; pasa a considerar el número de permutaciones de las letras del alfabeto y de los caballos de un establo de 20.

Un primer caso en el que se estudiaron cuestiones matemáticas aparentemente no relacionadas con la ayuda de permutaciones ocurrió alrededor de 1770, cuando Joseph Louis Lagrange, en el estudio de ecuaciones polinómicas, observó que las propiedades de las permutaciones de las raíces de una ecuación están relacionadas con las posibilidades de solucionarlo. Esta línea de trabajo finalmente resultó, a través del trabajo de Évariste Galois, en la teoría de Galois, que da una descripción completa de lo que es posible e imposible con respecto a la resolución de ecuaciones polinómicas (en una incógnita) por radicales. En las matemáticas modernas, hay muchas situaciones similares en las que comprender un problema requiere estudiar ciertas permutaciones relacionadas con él.

Permutaciones sin repeticiones

El ejemplo más simple de permutaciones es permutaciones sin repeticiones donde consideramos el número de posibles formas de organizar $n$ ítems en $n$ lugares. El factorial tiene una aplicación especial para definir el número de permutaciones en un conjunto que no incluye repeticiones. El número n!, leído "n factorial", es precisamente el número de maneras que podemos reorganizar las cosas en un nuevo orden. Por ejemplo, si tenemos tres frutas: una naranja, manzana y pera, podemos comerlas en el orden mencionado, o podemos cambiarlas (por ejemplo, una manzana, un pera y una naranja). El número exacto de permutaciones es entonces ${displaystyle 3!=1cdot 2cdot 3=6}$ . El número es extremadamente grande ya que el número de artículos (n) aumenta.

De manera similar, el número de arreglos de k elementos de objetos n se llama a veces una permutación parcial o una permutación k. Puede ser escrito como ${displaystyle nPk}$ (que lee "n permute k"), y es igual al número ${displaystyle n(n-1)cdots (n-k+1)}$ (también escrito como ${displaystyle n!/(n-k)!}$ ).

Definición

En los textos matemáticos es habitual denotar permutaciones utilizando letras griegas minúsculas. Comúnmente, tampoco. $alpha$ y $beta$ , o ${displaystyle sigmatau }$ y $pi$ se usan.

Las permutaciones se pueden definir como bijetillas de un conjunto $S$ en sí mismo. Todas las permutaciones de un conjunto con n elementos forman un grupo simétrico, denotado $S_{n}$ , donde la operación del grupo es la composición de la función. Así por dos permutaciones, $pi$ y $sigma$ en el grupo $S_{n}$ , los cuatro axiomas de grupo sostienen:

Cierre: Si $pi$ y $sigma$ están dentro $S_{n}$ entonces lo es ${displaystyle pi sigma.}$
Associatividad: Para cualquier tres permutaciones ${displaystyle pisigmatau in S_{n}}$ , ${displaystyle (pi sigma)tau =pi (sigma tau).}$
Identidad: Hay una permutación de identidad, denotada ${displaystyle operatorname {id} }$ y definidos por $operatorname {id} (x)=x$ para todos $xin S$ . Para cualquier $sigma in S_n$ , ${displaystyle operatorname {id} sigma =sigma operatorname {id} =sigma.}$
Invertibilidad: Por cada permutación ${displaystyle pi in S_{n}}$ , existe un permutación inversa ${displaystyle pi ^{-1}in S_{n}}$ Así que ${displaystyle pi pi ^{-1}=pi ^{-1}pi =operatorname {id}.}$

En general, la composición de dos permutaciones no es conmutativa, es decir, ${displaystyle pi sigma neq sigma pi.}$

Como una biyección de un conjunto a sí mismo, una permutación es una función que realiza un reordenamiento de un conjunto, y no es un arreglo en sí mismo. Un punto de vista más antiguo y más elemental es que las permutaciones son los propios arreglos. Para distinguir entre estos dos, los identificadores activo y pasivo a veces se anteponen al término permutación, mientras que en la terminología anterior sustituciones y permutaciones.

Una permutación se puede descomponer en una o más descomposición ciclos, es decir, las órbitas, que se encuentran rastreando repetidamente la aplicación de la permutación en algunos elementos. Por ejemplo, la permutación $sigma$ definidas por ${displaystyle sigma (7)=7}$ tiene 1 ciclo, ${displaystyle (,7,)}$ mientras que la permutación $pi$ definidas por ${displaystyle pi (2)=3}$ y ${displaystyle pi (3)=2}$ tiene 2 ciclos ${displaystyle (,2,3,)}$ (para más detalles sobre la sintaxis, véase § Ciclo notación abajo). En general, un ciclo de longitud k, es decir, consistente en k elementos, se llama k- ciclo.

Un elemento en un ciclo de 1 ${displaystyle (,x,)}$ se llama punto fijo de la permutación. Una permutación sin puntos fijos se llama un desglose. 2 ciclos se llaman transposiciones; tales permutaciones simplemente intercambian dos elementos, dejando los otros fijos.

Anotaciones

Dado que escribir permutaciones por elementos, es decir, como funciones por partes, es engorroso, se han inventado varias notaciones para representarlas de manera más compacta. La notación de ciclo es una opción popular para muchos matemáticos debido a su tamaño compacto y al hecho de que hace que la estructura de una permutación sea transparente. Es la notación que se usa en este artículo a menos que se especifique lo contrario, pero todavía se usan ampliamente otras notaciones, especialmente en áreas de aplicación.

Notación de dos líneas

En la notación de dos líneas de Cauchy, uno lista los elementos de S en la primera fila, y para cada uno su imagen debajo en la segunda fila. Por ejemplo, una permutación particular del conjunto S = {1, 2, 3, 4, 5} se puede escribir como

${displaystyle sigma ={begin{pmatrix}1&2&3&4&5\2&5&4&3&1end{pmatrix}};}$

esto significa que σ satisface $σ (1) = 2$ , $σ (2) = 5$ , $σ (3) = 4$ , <span class="texhtml" σ(4) = 3, y $σ (5) = 1$ . Los elementos de S pueden aparecer en cualquier orden en la primera fila. Esta permutación también podría escribirse como:

${displaystyle sigma ={begin{pmatrix}3&2&5&1&4\4&5&1&2&3end{pmatrix}},}$

${displaystyle sigma ={begin{pmatrix}5&1&4&3&2\1&2&3&4&5end{pmatrix}}.}$

Notación de una línea

Si hay un orden "natural" para los elementos S, di $x_{1},x_{2},ldotsx_{n}$ , entonces uno utiliza esto para la primera fila de la notación de dos líneas:

${displaystyle sigma ={begin{pmatrix}x_{1}&x_{2}&x_{3}&cdots &x_{n}\sigma (x_{1})&sigma (x_{2})&sigma (x_{3})&cdots &sigma (x_{n})end{pmatrix}}.}$

Bajo esta suposición, uno puede omitir la primera fila y escribir la permutación en notación de una línea como

${displaystyle (sigma (x_{1});sigma (x_{2});sigma (x_{3});cdots ;sigma (x_{n}))}$ ,

es decir, como una disposición ordenada de los elementos de S. Se debe tener cuidado para distinguir la notación de una línea de la notación de ciclo que se describe a continuación. En la literatura matemática, un uso común es omitir los paréntesis para la notación de una línea, mientras que se usan para la notación de ciclos. La notación de una línea también se denomina representación de palabras de una permutación. El ejemplo anterior sería 2 5 4 3 1 ya que se asumiría el orden natural 1 2 3 4 5 para el primer fila. (Es típico usar comas para separar estas entradas solo si algunas tienen dos o más dígitos). Esta forma es más compacta y es común en combinatoria elemental e informática. Es especialmente útil en aplicaciones donde los elementos de S o las permutaciones deben compararse como más grandes o más pequeños.

Notación de ciclo

La notación de ciclo describe el efecto de aplicar repetidamente la permutación en los elementos del conjunto. Expresa la permutación como producto de ciclos; dado que los ciclos distintos son disjuntos, esto se conoce como "descomposición en ciclos disjuntos".

Para escribir la permutación $sigma$ en la notación del ciclo, uno procede como sigue:

Escriba un soporte de apertura y seleccione un elemento arbitrario x de $S$ y escríbalo: ${displaystyle (,x}$
Luego rastrea la órbita de x; es decir, escriba sus valores bajo sucesivas aplicaciones $sigma$ : ${displaystyle (,x,sigma (x),sigma (sigma (x)),ldots }$
Repita hasta que el valor regrese a x y escribir un paréntesis de cierre en lugar de x: ${displaystyle (,x,sigma (x),sigma (sigma (x)),ldots ,)}$
Ahora continúe con un elemento Sí. de S, aún no escrito, y proceder de la misma manera: ${displaystyle (,x,sigma (x),sigma (sigma (x)),ldots ,)(,y,ldots ,)}$
Repita hasta todos los elementos S están escritos en ciclos.

Entonces, la permutación 2 5 4 3 1 (en notación de una línea) podría escribirse como (125)(34) en notación de ciclo.

Mientras que las permutaciones en general no conmutan, los ciclos disjuntos sí lo hacen; por ejemplo,

{displaystyle (,1,2,5,)(,3,4,)=(,3,4,)(,1,2,5,).}

{displaystyle (,1,2,5,)(,3,4,)=(,5,1,2,)(,3,4,)=(,2,5,1,)(,4,3,).}

1 ciclos se omiten a menudo de la notación del ciclo, siempre que el contexto sea claro; para cualquier elemento x dentro S no aparece en ningún ciclo, uno asume implícitamente ${displaystyle sigma (x)=x}$ . La permutación de identidad, que consiste sólo en 1 ciclos, puede ser denotada por un solo 1 ciclo (x), por el número 1, o por id.

Una característica conveniente de la notación cíclica es que la notación cíclica de la permutación inversa se obtiene invirtiendo el orden de los elementos en los ciclos de la permutación. Por ejemplo,

{displaystyle [(,1,2,5,)(,3,4,)]^{-1}=(,5,2,1,)(,4,3,).}

Notación de ciclo canónico

En algunos contextos combinatorios, es útil fijar un cierto orden para los elementos de los ciclos y de los ciclos (disjuntos) mismos. Miklós Bóna llama a las siguientes opciones de orden la notación de ciclo canónico:

en cada ciclo más grande elemento se enumera primero
los ciclos se clasifican en creciente orden de su primer elemento

Por ejemplo, (312)(54)(8)(976) es una permutación en notación de ciclo canónico. La notación de ciclo canónico no omite un ciclo.

Richard P. Stanley llama a la misma elección de representación la "representación estándar" de una permutación, y Martin Aigner usa el término "forma estándar" por la misma noción. Sergey Kitaev también utiliza el "formulario estándar" terminología, pero invierte ambas opciones; es decir, cada ciclo enumera primero su elemento mínimo y los ciclos se clasifican en orden decreciente de su mínimo, es decir, los primeros elementos.

Composición de permutaciones

Hay dos maneras de denotar la composición de dos permutaciones. ${displaystyle sigma cdot pi }$ es la función que mapea cualquier elemento x del conjunto ${displaystyle sigma (pi (x))}$ . La permutación más correcta se aplica al argumento primero, por la forma en que se escribe la aplicación de la función.

Puesto que la composición de la función es asociativa, así es la operación de composición en permutaciones: ${displaystyle (sigma pi)tau =sigma (pi tau)}$ . Por lo tanto, los productos de más de dos permutaciones se escriben generalmente sin agregar paréntesis a la agrupación expresa; también se escriben generalmente sin un punto u otro signo para indicar la composición.

Algunos autores prefieren que el factor más a la izquierda actúe primero, pero para ese fin, las permutaciones deben escribirse a la derecha de su argumento, a menudo como un exponente, donde σ actuando sobre x se escribe x^σ; entonces el producto se define por x^σ·π = (x^σ)^π. Sin embargo, esto da una regla diferente para multiplicar permutaciones; este artículo usa la definición donde se aplica primero la permutación más a la derecha.

Otros usos del término permutación

El concepto de una permutación como un arreglo ordenado admite varias generalizaciones que no son permutaciones, pero que han sido llamadas permutaciones en la literatura.

K-permutaciones de n

Un significado más débil del término permutación, a veces utilizado en textos combinatorios elementales, designa los arreglos ordenados en los que ningún elemento ocurre más de una vez, pero sin el requisito de utilizar todos los elementos de un determinado conjunto. Estas no son permutaciones excepto en casos especiales, pero son generalizaciones naturales del concepto de arreglo ordenado. De hecho, este uso a menudo implica considerar arreglos de una longitud fijak of elements taken from a given set of size n, en otras palabras, estos k-permutaciones de n son los diferentes arreglos ordenados de un k-element subset of an n-set (a veces llamado variaciones o arreglos en literatura antigua). Estos objetos también se conocen como permutaciones parciales o como secuencias sin repetición, términos que evitan la confusión con el otro, más común, significado de "permutación". El número de tales $k$ -permutaciones de $n$ es denotado varias veces por símbolos como $P_{k}^{n}$ , $_{n}P_{k}$ , $^{n}P_{k}$ , $P_{n,k}$ , o $P(n,k)$ , y su valor es dado por el producto

$P(n,k)=underbrace {ncdot (n-1)cdot (n-2)cdots (n-k+1)} _{k mathrm {factors} }$ ,

que es 0 cuando k > n, y de lo contrario es igual a

${frac {n!}{(n-k)!}}.$

El producto está bien definido sin la suposición de que $n$ es un entero no negativo, y es de importancia fuera de la combinatoria también; se conoce como el símbolo Pochhammer $(n)_{k}$ o como $k$ - la caída del poder factorial $n^{underline {k}}$ de $n$ .

Este uso del término permutación está estrechamente relacionado con el término combinación. Una combinación de elementos k de un conjunto n S es un subconjunto de elementos k de S, cuyos elementos no están ordenados. Tomando todos los subconjuntos de elementos k de S y ordenando cada uno de ellos de todas las formas posibles, obtenemos todas las permutaciones k de S. El número de combinaciones k de un conjunto n, C(n,k), por lo tanto, está relacionado con el número de k-permutaciones de n por:

${displaystyle C(n,k)={frac {P(n,k)}{P(k,k)}}={frac {tfrac {n!}{(n-k)!}}{tfrac {k!}{0!}}}={frac {n!}{(n-k)!,k!}}.}$

Estos números también se conocen como coeficientes binomiales y son denotados por ${binom {n}{k}}$ .

Permutaciones con repetición

Disposiciones ordenadas k elementos de un conjunto S, donde se permite la repetición, se llaman k-tuples. They have sometimes been referred to as permutaciones con repetición, aunque no son permutaciones en general. También se les llama palabras sobre el alfabeto S en algunos contextos. Si el conjunto S tiene n elementos, el número de k-tuples over S es ${displaystyle n^{k}.}$ No hay ninguna restricción sobre cuán a menudo puede aparecer un elemento en un k-tuple, pero si se imponen restricciones sobre cuán a menudo puede aparecer un elemento, esta fórmula ya no es válida.

Permutaciones de multiconjuntos

Permutaciones de multisets

Si M es un multiset finito, luego un permutación multiset es un arreglo ordenado de elementos de M en que cada elemento aparece una serie de veces igual a su multiplicidad M. Un anagrama de una palabra que tiene algunas cartas repetidas es un ejemplo de una permutación multiset. Si las multiplicidades de los elementos M (tomada en algún orden) $m_{1}$ , $m_{2}$ ,... $m_{l}$ y su suma (es decir, el tamaño de M) es n, entonces el número de permutaciones multiset M es dado por el coeficiente multinomio,

${displaystyle {n choose m_{1},m_{2},ldotsm_{l}}={frac {n!}{m_{1}!,m_{2}!,cdots ,m_{l}!}}={frac {left(sum _{i=1}^{l}{m_{i}}right)!}{prod _{i=1}^{l}{m_{i}!}}}.}$

Por ejemplo, el número de anagramas distintos de la palabra MISSISSIPPI es:

${displaystyle {frac {11!}{1!,4!,4!,2!}}=34650}$ .

Una k-permutación de un multiconjunto M es una secuencia de longitud k de elementos de M en el que cada elemento aparece un número de veces menor o igual que su multiplicidad en M (el número de repetición de un elemento ).

Permutaciones circulares

Las permutaciones, cuando se consideran arreglos, a veces se denominan arreglos ordenados linealmente. En estos arreglos hay un primer elemento, un segundo elemento, y así sucesivamente. Sin embargo, si los objetos están dispuestos de manera circular, este orden distinguido ya no existe, es decir, no hay un "primer elemento" en el arreglo, cualquier elemento puede ser considerado como el inicio del arreglo. Los arreglos de objetos en forma circular se llaman permutaciones circulares. Estos se pueden definir formalmente como clases de equivalencia de permutaciones ordinarias de los objetos, para la relación de equivalencia generada al mover el elemento final del arreglo lineal hacia su frente.

Dos permutaciones circulares son equivalentes si una se puede rotar en la otra (es decir, hacer un ciclo sin cambiar las posiciones relativas de los elementos). Las siguientes cuatro permutaciones circulares en cuatro letras se consideran iguales.

 1 4 2 3
4 3 2 1 3 4 1 2
2 3 1 4

Los arreglos circulares deben leerse en sentido contrario a las agujas del reloj, por lo que los dos siguientes no son equivalentes ya que ninguna rotación puede acercar uno al otro.

 1 1 1
4 3 3 4
2

El número de permutaciones circulares de un conjunto S con n elementos es (n – 1)!.

Propiedades

El número de permutaciones de $n$ objetos distintos es $n$ !.

El número de $n$ -permutaciones con $k$ disjuntas ciclos es el número de Stirling sin signo del primer tipo, denotado por $c (n, k).$

Tipo de ciclo

Los ciclos (incluyendo los puntos fijos) de una permutación $sigma$ de un conjunto con $n$ elementos partición que se establece; así las longitudes de estos ciclos forman una partición entero de $n$ , que se llama el Tipo de ciclo (o a veces estructura del ciclo o Forma del ciclo) de $sigma$ . Hay un "1" en el tipo de ciclo para cada punto fijo $sigma$ , un "2" para cada transposición, y así sucesivamente. El tipo de ciclo ${displaystyle beta =(1,2,5,)(,3,4,)(6,8,)(,7,)}$ es ${displaystyle (3,2,2,1).}$

Esto también puede ser escrito en una forma más compacta $[1] 12231]$ . Más precisamente, la forma general es ${displaystyle [1^{alpha _{1}}2^{alpha _{2}}dotsm n^{alpha _{n}}]}$ , donde $alpha _{1},ldotsalpha _{n}$ son los números de ciclos de longitud respectiva. El número de permutaciones de un tipo de ciclo dado es

${displaystyle {frac {n!}{1^{alpha _{1}}2^{alpha _{2}}dotsm n^{alpha _{n}}alpha _{1}!alpha _{2}!dotsm alpha _{n}!}}}$ .

Conjugar permutaciones

En general, la composición de permutaciones escritas en notación de ciclos no sigue un patrón fácilmente descrito – los ciclos de la composición pueden ser diferentes de los que se componen. Sin embargo, el tipo de ciclo se conserva en el caso especial de conjugar una permutación $sigma$ por otra permutación $pi$ , lo que significa formar el producto ${displaystyle pi sigma pi ^{-1}}$ . Aquí, ${displaystyle pi sigma pi ^{-1}}$ es conjugado de $sigma$ por $pi$ y su notación de ciclo se puede obtener tomando la notación de ciclo para $sigma$ y aplicación $pi$ a todas las entradas. Sigue que dos permutaciones son conjugadas exactamente cuando tienen el mismo tipo de ciclo.

Orden de permutación

El orden de una permutación $sigma$ es el entero positivo más pequeño m así ${displaystyle sigma ^{m}=mathrm {id} }$ . Es el múltiplo menos común de sus ciclos longitudes. Por ejemplo, el orden de ${displaystyle (,1,3,2)(,4,5,)}$ es ${displaystyle 2cdot 3=6}$ .

Paridad de una permutación

Cada permutación de un conjunto finito se puede expresar como el producto de transposiciones. Aunque pueden existir muchas expresiones de este tipo para una permutación dada, todas contienen un número par de transposiciones o todas contienen un número impar de transposiciones. Por lo tanto, todas las permutaciones se pueden clasificar como pares o impares según este número.

Este resultado se puede ampliar para asignar un Signatura, escrito ${displaystyle operatorname {sgn} sigma }$ , a cada permutación. ${displaystyle operatorname {sgn} sigma =+1}$ si $sigma$ es incluso ${displaystyle operatorname {sgn} sigma =-1}$ si $sigma$ Es extraño. Entonces para dos permutaciones $sigma$ y $pi$

${displaystyle operatorname {sgn} (sigma pi)=operatorname {sgn} sigma cdot operatorname {sgn} pi.}$

De ello se desprende que ${displaystyle operatorname {sgn} left(sigma sigma ^{-1}right)=+1.}$

Representación matricial

A matriz de permutación es una matriz n × n que tiene exactamente una entrada 1 en cada columna y en cada fila, y todas las demás entradas son 0. Hay varias convenciones diferentes que se pueden utilizar para asignar una matriz de permutación a una permutación de {1, 2,..., n}. Un enfoque natural es asociarse a la permutación σ la matriz ${displaystyle M_{sigma }}$ cuyoi, j) entrada es 1 si i = σ()j) y es 0 de lo contrario. Esta convención tiene dos propiedades atractivas: primero, el producto de matrices y de permutaciones está en el mismo orden, es decir, ${displaystyle M_{sigma }M_{pi }=M_{sigma circ pi }}$ para todas las permutaciones σ y π. Segundo, si ${displaystyle {bf {e}}_{i}}$ representa el estándar $ntimes 1$ vector de columna (el vector con it entrada igual a 1 y todas las demás entradas iguales a 0), entonces ${displaystyle M_{sigma }{bf {e}}_{i}={bf {e}}_{sigma (i)}}$ .

Por ejemplo, con esta convención, la matriz asociada a la permutación ${displaystyle sigma (1,2,3)=(2,1,3)}$ es ${displaystyle {begin{pmatrix}0&1&0\1&0&0\0&0&1end{pmatrix}}}$ y la matriz asociada a la permutación ${displaystyle pi (1,2,3)=(2,3,1)}$ es ${displaystyle {begin{pmatrix}0&0&1\1&0&0\0&1&0end{pmatrix}}}$ . Entonces la composición de las permutaciones es ${displaystyle (sigma circ pi)(1,2,3)=sigma (2,3,1)=(1,3,2)}$ , y el producto matriz correspondiente

{displaystyle M_{(2,1,3)}M_{(2,3,1)}={begin{pmatrix}0&1&0\1&0&0\0&0&1end{pmatrix}}{begin{pmatrix}0&0&1\1&0&0\0&1&0end{pmatrix}}={begin{pmatrix}1&0&0\0&0&1\0&1&0end{pmatrix}}=M_{(1,3,2)}.}

Composición de permutaciones correspondientes a una multiplicación de matrices de permutación.

También es común en la literatura encontrar la convención inversa, donde una permutación σ se asocia a la matriz ${displaystyle P_{sigma }=(M_{sigma })^{-1}=(M_{sigma })^{T}}$ cuyoi, j) entrada es 1 si j = σ()i) y es 0 de lo contrario. En esta convención, las matrices de permutación se multiplican en el orden opuesto de las permutaciones, es decir, ${displaystyle P_{sigma }P_{pi }=P_{pi circ sigma }}$ para todas las permutaciones σ y π. En esta correspondencia, las matrices de permutación actúan permutando índices de estándar ${displaystyle 1times n}$ vectores de fila ${displaystyle ({bf {e}}_{i})^{T}}$ : uno tiene ${displaystyle ({bf {e}}_{i})^{T}P_{sigma }=({bf {e}}_{sigma (i)})^{T}}$ .

La tabla de Cayley a la derecha muestra estas matrices para permutaciones de 3 elementos.

Permutaciones de conjuntos totalmente ordenados

En algunas aplicaciones, los elementos del conjunto que se permutan se compararán entre sí. Esto requiere que el conjunto S tenga un orden total para que se puedan comparar dos elementos cualesquiera. El conjunto {1, 2,..., n} está totalmente ordenado por el habitual "≤" relación, por lo que es el conjunto más utilizado en estas aplicaciones, pero en general, cualquier conjunto totalmente ordenado servirá. En estas aplicaciones, se necesita la vista de disposición ordenada de una permutación para hablar sobre las posiciones en una permutación.

Hay una serie de propiedades que están directamente relacionadas con el orden total de S.

Ascensos, descensos, carreras y superaciones

Un ascenso de una permutación σ de n es cualquier posición i < n donde el siguiente valor es mayor que el actual. Es decir, si σ = σ₁σ₂...σ_n, entonces i es un ascenso si σ_i < σ_i+1.

Por ejemplo, la permutación 3452167 tiene ascensos (en las posiciones) 1, 2, 5 y 6.

Análogamente, a descenso es una posición i.n con σ_i■σ_{i+ 1}Así que todos i con $<math alttext="{displaystyle 1leq i1\leq \leq i.n{displaystyle 1leq I didn't} <img alt="{displaystyle 1leq i$ o es un ascenso o es un descensoσ.

Una ejecución ascendente de una permutación es una subsecuencia contigua creciente no vacía de la permutación que no puede extenderse en ningún extremo; corresponde a una secuencia máxima de subidas sucesivas (esta última puede estar vacía: entre dos bajadas sucesivas sigue habiendo un recorrido ascendente de longitud 1). Por el contrario, una subsecuencia creciente de una permutación no es necesariamente contigua: es una secuencia creciente de elementos obtenidos de la permutación al omitir los valores en algunas posiciones. Por ejemplo, la permutación 2453167 tiene las secuencias ascendentes 245, 3 y 167, mientras que tiene una subsecuencia creciente 2367.

Si una permutación tiene k − 1 descensos, entonces debe ser la unión de k tramos ascendentes.

Número de permutaciones n con k ascensión es (por definición) el número Eulerian $textstyle leftlangle {n atop k}rightrangle$ ; este es también el número de permutaciones n con k descensos. Algunos autores definen sin embargo el número de Eulerian $textstyle leftlangle {n atop k}rightrangle$ como el número de permutaciones con k carreras ascendentes, que corresponden a k − 1 descensos.

Una excedencia de una permutación σ₁σ₂...σ_n es un índice j tal que σ_j > j. Si la desigualdad no es estricta (es decir, σ_j ≥ j ), entonces j se denomina excedencia débil. El número de n-permutaciones con k excedencias coincide con el número de n-permutaciones con k descensos.

Lema de transición de Foata

Hay una relación entre la notación de una línea y la notación de ciclo canónico. Considere la permutación ${displaystyle (,2,)(,3,1,)}$ en notación de ciclo canónico; si simplemente quitamos las paréntesis, obtenemos la permutación ${displaystyle 231}$ en notación de una línea. La lema de transición de Foata establece la naturaleza de esta correspondencia como una bijeción en el conjunto de n-permutaciones (a sí misma). Richard P. Stanley llama a esta correspondencia bijeción fundamental.

Vamos ${displaystyle f(p)=q}$ ser la transformación parentheses-eraing que devuelve $q$ en la notación de una línea cuando se $p$ en notación de ciclo canónico. As stated, $f$ funciona simplemente eliminando todos los paréntesis. La operación de la transformación inversa, ${displaystyle f^{-1}(q)=p}$ , que regresa $p$ en la notación del ciclo canónico cuando se $q$ en la notación de una línea, es un poco menos intuitivo. Dada la notación de una línea $q=q_{1}q_{2}cdots q_{n}$ , el primer ciclo de $p$ en la notación del ciclo canónico debe comenzar con $q_{1}$ . Mientras los elementos posteriores sean más pequeños que $q_{1}$ , estamos en el mismo ciclo de $p$ . El segundo ciclo $p$ comienza en el índice más pequeño $j$ tales que $q_{1}}" xmlns="http://www.w3.org/1998/Math/MathML">qj■q1{displaystyle q_{j} títuloq_{1}q_{1}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c7e20ee0ce5a7e6af06f506677649926a7581628" style="vertical-align: -1.005ex; width:7.136ex; height:2.509ex;"/>$ . En otras palabras, $q_{j}$ es más grande que todo lo demás a su izquierda, así que se llama máximo izquierdo a derecho. Cada ciclo de la notación del ciclo canónico comienza con un máximo de izquierda a derecha.

Por ejemplo, en la permutación ${displaystyle q=312548976}$ , 5 es el primer elemento más grande que el elemento de inicio 3, por lo que el primer ciclo $p$ Debe ser ${displaystyle (,3,1,2,)}$ . Luego 8 es el siguiente elemento más grande que 5, por lo que el segundo ciclo es ${displaystyle (,5,4,)}$ . Puesto que 9 es más grande que 8, ${displaystyle (,8,)}$ es un ciclo por sí mismo. Finalmente, 9 es más grande que todos los elementos restantes a su derecha, por lo que el último ciclo es ${displaystyle (,9,7,6,)}$ . Concatenando estos 4 ciclos da ${displaystyle p=(,3,1,2,)(,5,4,)(,8,)(,9,7,6,)}$ en notación de ciclo canónico.

El cuadro siguiente muestra ambos $q$ y $p$ para las seis permutaciones de $123$ . El lado audaz de cada igualdad muestra la permutación utilizando su notación designada (notación de una línea para $q$ notación de ciclo canónico para $p$ ) mientras que el lado no-bold muestra la misma permutación en la otra notación. Comparando el lado audaz de cada columna de la tabla muestra la operación de eliminación/retorno de la bijeción de Foata, comparando al mismo lado de cada columna (por ejemplo, el LHS) muestra qué permutaciones se mapean a sí mismos por la bijección (primeras 3 filas) y que no son (las 3 filas).

${displaystyle q=f(p)}$	${displaystyle p=f^{-1}(q)}$
${displaystyle mathbf {123} =(,1,)(,2,)(,3,)}$	${displaystyle 123=mathbf {(,1,)(,2,)(,3,)} }$
${displaystyle mathbf {132} =(,1,)(,3,2,)}$	${displaystyle 132=mathbf {(,1,)(,3,2,)} }$
${displaystyle mathbf {213} =(,2,1,)(,3,)}$	${displaystyle 213=mathbf {(,2,1,)(,3,)} }$
${displaystyle mathbf {231} =(,3,1,2,)}$	${displaystyle 321=mathbf {(,2,)(,3,1,)} }$
${displaystyle mathbf {312} =(,3,2,1,)}$	${displaystyle 231=mathbf {(,3,1,2,)} }$
${displaystyle mathbf {321} =(,2,)(,3,1,)}$	${displaystyle 312=mathbf {(,3,2,1,)} }$

Como primer corolario, el número de n-permutaciones con exactamente k maxima izquierda a derecha también es igual a la insignia Número de primera clase, $c(n,k)$ . Además, el mapeo de Foata toma un n-permutación con k-excedencias débiles a un n-permutaciones con k − 1 ascensos. Por ejemplo, (2)(31) = 321 tiene dos excesiones débiles (en el índice 1 y 2), mientras que f(321) = 231 tiene un ascenso (en el índice 1; es decir, de 2 a 3).

Inversiones

En el 15 rompecabezas el objetivo es conseguir los cuadrados en orden ascendente. Las posiciones iniciales que tienen un número impar de inversiones son imposibles de resolver.

An inversión de una permutaciónσ es un par $() i, j)$ de posiciones donde las entradas de una permutación están en el orden opuesto: $<math alttext="{displaystyle ii.j{displaystyle i donej} <img alt="i$ y $sigma _{j}}" xmlns="http://www.w3.org/1998/Math/MathML">σ σ i■σ σ j{displaystyle sigma _{i} títulosigma _{j}sigma _{j}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0ee74babc7949f9e9f93d99ea2733ed93902c658" style="vertical-align: -1.005ex; width:7.463ex; height:2.509ex;"/>$ . Así que un descenso es sólo una inversión en dos posiciones adyacentes. Por ejemplo, la permutación σ = 23154 tiene tres inversiones: (1, 3), (2, 3), y (4, 5), para los pares de entradas (2, 1), (3, 1), y (5, 4).

A veces, una inversión se define como el par de valores $(σ i, σ j)$ cuyo orden es inverso; esto no hace ninguna diferencia para el número de inversiones, y este par (invertido) también es una inversión en el sentido anterior para la permutación inversa σ⁻¹. El número de inversiones es una medida importante del grado en que las entradas de una permutación están desordenadas; es lo mismo para σ y para σ⁻¹. Poner en orden una permutación con inversiones k (es decir, transformarla en la permutación identidad), aplicando sucesivamente (multiplicación a la derecha por) transposiciones adyacentes, siempre es posible y requiere una secuencia de k dichas operaciones. Además, cualquier elección razonable para las transposiciones adyacentes funcionará: basta con elegir en cada paso una transposición de i y i + 1 donde i es un descenso de la permutación modificada hasta el momento (de modo que la transposición eliminará este descenso en particular, aunque podría crear otros descensos). Esto es así porque la aplicación de dicha transposición reduce el número de inversiones en 1; mientras este número no sea cero, la permutación no es la identidad, por lo que tiene al menos una descendencia. La ordenación por burbuja y la ordenación por inserción pueden interpretarse como instancias particulares de este procedimiento para ordenar una secuencia. Dicho sea de paso, este procedimiento demuestra que cualquier permutación σ puede escribirse como un producto de transposiciones adyacentes; pues éste puede simplemente invertir cualquier secuencia de tales transposiciones que transforme σ en la identidad. De hecho, al enumerar todas las secuencias de transposiciones adyacentes que transformarían σ en la identidad, se obtiene (después de la inversión) una lista completa de todas las expresiones de longitud mínima escribiendo σ como producto de transposiciones adyacentes.

El número de permutaciones de n con inversiones k se expresa mediante un número mahoniano, es el coeficiente de X^k en la expansión del producto

{displaystyle prod _{m=1}^{n}sum _{i=0}^{m-1}X^{i}=1left(1+Xright)left(1+X+X^{2}right)cdots left(1+X+X^{2}+cdots +X^{n-1}right),}

qXn_q
Vamos ${displaystyle sigma in S_{n},i,jin {1,2,dotsn}}$ tales que $<math alttext="{displaystyle ii.j{displaystyle i donej} <img alt="i$ y $sigma (j)}" xmlns="http://www.w3.org/1998/Math/MathML">σ σ ()i)■σ σ ()j){displaystyle sigma (i) títulosigma (j)}sigma (j)}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/52aca6b87bcb609932fb127b26272a84330db0ef" style="vertical-align: -0.838ex; width:11.137ex; height:2.843ex;"/>$ . En este caso, diga el peso de la inversión $(i,j)$ es ${displaystyle sigma (i)-sigma (j)}$ . Kobayashi (2011) demostró la fórmula de enumeración
$<math alttext="{displaystyle sum _{isigma (j)}(sigma (i)-sigma (j))=|{tau in S_{n}mid tau leq sigmatau {text{ is bigrassmannian}}}}" display="block" xmlns="http://www.w3.org/1998/Math/MathML">.. i.j,σ σ ()i)■σ σ ()j)()σ σ ()i)− − σ σ ()j))=Silencio{}τ τ ▪ ▪ Sn▪ ▪ τ τ ≤ ≤ σ σ ,τ τ es bigrassmannian}{displaystyle sum _{iَj,sigma (i)}sigma (j)}(sigma (i)-sigma (j))= arrest{tau in S_{n}mid tau leq sigmatau {text{ is bigrassmannian}}}<img alt="{displaystyle sum _{isigma (j)}(sigma (i)-sigma (j))=|{tau in S_{n}mid tau leq sigmatau {text{ is bigrassmannian}}}}" aria-hidden="true" class="mwe-math-fallback-image-display" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5f0f29cf06daca053ddc9b68676de3895dded81" style="vertical-align: -3.505ex; width:63.709ex; height:6.009ex;"/>$
Donde $leq$ denota orden Bruhat en los grupos simétricos. Este orden parcial con frecuencia aparece en el contexto de los grupos de Coxeter.
Permutaciones en informática
Permutaciones de numeración
Una forma de representar permutaciones de n cosas es mediante un número entero N con 0 ≤ N < n!, siempre que se proporcionen métodos convenientes para convertir entre el número y la representación de una permutación como un arreglo ordenado (secuencia). Esto da la representación más compacta de permutaciones arbitrarias, y en computación es particularmente atractivo cuando n es lo suficientemente pequeño como para que N se pueda contener en una palabra de máquina; para palabras de 32 bits esto significa n ≤ 12, y para palabras de 64 bits esto significa n ≤ 20. La conversión se puede realizar a través de la forma intermedia de una secuencia de números d_n, d_n−1,..., d₂, d₁, donde d_i es un número entero no negativo menor que i (se puede omitir d₁, ya que siempre es 0, pero su presencia hace que la posterior conversión a una permutación sea más fácil de describir). Entonces, el primer paso es simplemente expresar N en el sistema numérico factorial, que es solo una representación de base mixta particular, donde, para números menores que n!, las bases (valores posicionales o factores de multiplicación) para los dígitos sucesivos son (n − 1)!, (n − 2)!,..., 2!, 1!. El segundo paso interpreta esta secuencia como un código Lehmer o (casi de manera equivalente) como una tabla de inversión.
Diagrama de rotación para ${displaystyle sigma =(6,3,8,1,4,9,7,2,5)}$
^σ_i
_i
1 2 3 4 5 6 7 8 9 Código Lehmer
1 × × × × × • d₉ = 5
2 × × • d₈ = 2
3 × × × × × • d₇ = 5
4 • d₆ = 0
5 × • d₅ = 1
6 × × × • d₄ = 3
7 × × • d₃ = 2
8 • d₂ = 0
9 • d₁ = 0
Tabla de inversión 3 6 1 2 4 0 2 0 0
En el código Lehmer para una permutación σ, el número d_n representa la elección hecha para el primer término σ₁, el número d_n−1 representa la elección hecha para el segundo término σ₂ entre los restantes n − 1 elementos del conjunto, y así sucesivamente. Más precisamente, cada d_n+1−i da el número de restantes elementos estrictamente menores que el término σ_i. Dado que esos elementos restantes están obligados a aparecer como algún término posterior σ_j, el dígito d_n+1−i cuenta las inversiones (i,j) con i como índice más pequeño (el número de valores j para los que i < j y σ_i > σ_j). La tabla de inversión para σ es bastante similar, pero aquí d_{n+1− k} cuenta el número de inversiones (i,j) donde k = σ_j aparece como el menor de los dos valores que aparecen en orden inverso. Ambas codificaciones se pueden visualizar mediante un n por n diagrama de Rothe (llamado así por Heinrich August Rothe) en el que los puntos en (i,σ_i) marca las entradas de la permutación, y una cruz en (i,σ_j) marca la inversión (i,j); por la definición de inversiones, una cruz aparece en cualquier cuadrado que viene antes del punto (j,σ_j) en su columna, y antes del punto (i,σ_i) en su fila. El código de Lehmer enumera el número de cruces en filas sucesivas, mientras que la tabla de inversión enumera el número de cruces en columnas sucesivas; es simplemente el código de Lehmer para la permutación inversa, y viceversa.
Para convertir efectivamente un código Lehmer d_n, d_n−1,..., d₂, d₁ en una permutación de un conjunto ordenado S, uno puede comenzar con una lista de los elementos de S en orden creciente, y para i aumentando de 1 a n establece σ_i en el elemento de la lista precedido por d_n+1−i otros, y elimine ese elemento de la lista. Para convertir una tabla de inversión d_n, d_n−1,..., d₂, d₁ en la permutación correspondiente, uno puede atravesar los números de d₁ a d_n al insertar los elementos de S de mayor a menor en una secuencia inicialmente vacía; en el paso usando el número d de la tabla de inversión, el elemento de S insertado en la secuencia en el punto donde está precedido por d elementos ya presentes. Alternativamente, uno podría procesar los números de la tabla de inversión y los elementos de S ambos en el orden opuesto, comenzando con una fila de n espacios vacíos, y en cada paso colocar el elemento de S en la ranura vacía que está precedida por d otras ranuras vacías.
La conversión de números naturales sucesivos al sistema de numeración factorial produce esas secuencias en orden lexicográfico (como es el caso con cualquier sistema numérico de base mixta), y su posterior conversión a permutaciones conserva el orden lexicográfico, siempre que se utilice la interpretación del código de Lehmer (usando tablas de inversión, uno obtiene un orden diferente, donde uno comienza comparando permutaciones por el lugar de sus entradas 1 en lugar de por el valor de sus primeras entradas). La suma de los números en la representación del sistema numérico factorial da el número de inversiones de la permutación, y la paridad de esa suma da la firma de la permutación. Además, las posiciones de los ceros en la tabla de inversión dan los valores de los máximos de la permutación de izquierda a derecha (en el ejemplo 6, 8, 9) mientras que las posiciones de los ceros en el código de Lehmer son las posiciones de la derecha -mínimos a la izquierda (en el ejemplo posiciona el 4, 8, 9 de los valores 1, 2, 5); esto permite calcular la distribución de dichos extremos entre todas las permutaciones. Una permutación con código Lehmer d_n, d_n−1,..., d₂, d₁ tiene un ascenso n − i si y solo si d_i ≥ d_i+1.
Algoritmos para generar permutaciones
En computación, puede ser necesario generar permutaciones de una secuencia dada de valores. Los métodos mejor adaptados para hacer esto dependen de si se desean algunas permutaciones elegidas al azar o todas las permutaciones y, en este último caso, si se requiere un orden específico. Otra cuestión es si se debe tener en cuenta la posible igualdad entre las entradas en la secuencia dada; si es así, solo se deben generar distintas permutaciones de conjuntos múltiples de la secuencia.
Una forma obvia de generar permutaciones de n es generar valores para el código de Lehmer (¡posiblemente usando la representación del sistema de numeración factorial de enteros hasta n!), y convertirlos en las permutaciones correspondientes. Sin embargo, el último paso, aunque sencillo, es difícil de implementar de manera eficiente, porque requiere n operaciones, cada una de selección de una secuencia y eliminación de ella, en una posición arbitraria; de las representaciones obvias de la secuencia como una matriz o una lista enlazada, ambas requieren (por diferentes razones) alrededor de n²/4 operaciones para realizar la conversión. Dado que es probable que n sea bastante pequeño (especialmente si se necesita la generación de todas las permutaciones), eso no es un gran problema, pero resulta que tanto para la generación aleatoria como para la sistemática existen alternativas simples que hacerlo considerablemente mejor. Por esta razón no parece útil, aunque ciertamente posible, emplear una estructura de datos especial que permita realizar la conversión de código Lehmer a permutación en tiempo O(n log n).
Generación aleatoria de permutaciones
Para generar permutaciones aleatorias de una secuencia dada de valores n, no importa si se aplica una permutación aleatoria de n a la secuencia o se elige una permutación aleatoria. elemento del conjunto de permutaciones distintas (multiconjunto) de la secuencia. Esto se debe a que, aunque en el caso de valores repetidos puede haber muchas permutaciones distintas de n que dan como resultado la misma secuencia permutada, el número de tales permutaciones es el mismo para cada resultado posible. A diferencia de la generación sistemática, que se vuelve inviable para grandes n debido al crecimiento del número n!, no hay razón para suponer que n será pequeño para la generación aleatoria.
¡La idea básica para generar una permutación aleatoria es generar al azar uno de los n! secuencias de números enteros d₁,d₂,...,d_n que satisface $0 \leq d i < i$ (dado que d₁ siempre es cero, puede omitirse) y convertirlo en una permutación a través de una correspondencia biyectiva. Para la última correspondencia se podría interpretar la secuencia (inversa) como un código de Lehmer, y esto da un método de generación publicado por primera vez en 1938 por Ronald Fisher y Frank Yates. Si bien en ese momento la implementación de la computadora no era un problema, este método adolece de la dificultad esbozada anteriormente para convertir de código Lehmer a permutación de manera eficiente. Esto se puede remediar usando una correspondencia biyectiva diferente: después de usar d_i para seleccionar un elemento entre los i restantes elementos de la secuencia (para valores decrecientes de i), en lugar de eliminar el elemento y compactar la secuencia desplazando más elementos hacia abajo un lugar, se intercambia el elemento con el último elemento restante. Por lo tanto, los elementos que quedan para la selección forman un rango consecutivo en cada punto en el tiempo, aunque no aparezcan en el mismo orden en que lo hicieron en la secuencia original. El mapeo de la secuencia de enteros a las permutaciones es algo complicado, pero se puede ver que produce cada permutación exactamente de una manera, por inducción inmediata. Cuando el elemento seleccionado resulta ser el último elemento restante, se puede omitir la operación de intercambio. Esto no ocurre con la frecuencia suficiente para justificar la prueba de la condición, pero el elemento final debe incluirse entre los candidatos de la selección, para garantizar que se puedan generar todas las permutaciones.
El algoritmo resultante para generar una permutación aleatoria de a[0], a[1],..., a[n − 1] se puede describir de la siguiente manera en pseudocódigo:
para i desde n abajo 2 do d_i ← elemento aleatorio de { 0,..., i − 1 } Swap a[d_i] y a[i − 1
Esto se puede combinar con la inicialización de la matriz a[i] = i de la siguiente manera
para i desde 0 a n−1 do d_{i+ 1} ← elemento aleatorio de { 0,..., i } a[i← a[d_{i+ 1}] a[d_{i+ 1}← i
Si d_i+1 = i, la primera asignación copiará un valor no inicializado, pero el segundo lo sobrescribirá con el valor correcto i.
Sin embargo, Fisher-Yates no es el algoritmo más rápido para generar una permutación, porque Fisher-Yates es esencialmente un algoritmo secuencial y "divide y vencerás" los procedimientos pueden lograr el mismo resultado en paralelo.
Generación en orden lexicográfico
Hay muchas formas de generar sistemáticamente todas las permutaciones de una secuencia determinada. Un algoritmo clásico, simple y flexible se basa en encontrar la siguiente permutación en el ordenamiento lexicográfico, si existe. Puede manejar valores repetidos, en cuyo caso genera cada permutación distinta de conjuntos múltiples una vez. Incluso para permutaciones ordinarias es significativamente más eficiente que generar valores para el código Lehmer en orden lexicográfico (posiblemente utilizando el sistema numérico factorial) y convertirlos en permutaciones. Comienza clasificando la secuencia en orden (débilmente) creciente (lo que da su permutación lexicográficamente mínima), y luego repite avanzando a la siguiente permutación siempre que se encuentre una. El método se remonta a Narayana Pandita en la India del siglo XIV y ha sido redescubierto con frecuencia.
El siguiente algoritmo genera la siguiente permutación lexicográficamente después de una permutación determinada. Cambia la permutación dada en el lugar.
Encontrar el índice más grande k tales que a[k] a[k + 1]. Si no existe tal índice, la permutación es la última permutación.
Encontrar el índice más grande l más grande que k tales que a[k] a[l].
Cierre el valor de a[kCon la de a[l].
Invierte la secuencia de a[k + 1] hasta e incluyendo el elemento final a[n].
Por ejemplo, dada la secuencia [1, 2, 3, 4] (que está en orden creciente), y dado que el índice está basado en cero, los pasos son los siguientes:
Índice k = 2, porque 3 se coloca en un índice que satisface la condición de ser el índice más grande que es todavía menos que a[k + 1] que es 4.
Índice l = 3, porque 4 es el único valor en la secuencia que es mayor que 3 para satisfacer la condición a[k] a[l].
Los valores de a[2] y a[3] se intercambian para formar la nueva secuencia [1, 2, 4, 3].
La secuencia después k-index a[2] al elemento final se invierte. Porque sólo un valor reside después de este índice (el 3), la secuencia permanece inalterada en este caso. Así el sucesor lexicográfico del estado inicial está permutado: [1, 2, 4, 3].
Siguiendo este algoritmo, la siguiente permutación lexicográfica será [1, 3, 2, 4], y la permutación 24 será [4, 3, 2, 1] en cuyo punto a[ k] < a[k + 1] no existe, lo que indica que esta es la última permutación.
Este método utiliza alrededor de 3 comparaciones y 1,5 intercambios por permutación, amortizado en toda la secuencia, sin contar la ordenación inicial.
Generación con cambios mínimos
Una alternativa al algoritmo anterior, el algoritmo Steinhaus-Johnson-Trotter, genera un orden en todas las permutaciones de una secuencia determinada con la propiedad de que dos permutaciones consecutivas cualesquiera en su salida difieren al intercambiar dos valores adyacentes. Este orden en las permutaciones era conocido por los campaneros ingleses del siglo XVII, entre los cuales se conocía como "cambios simples". Una ventaja de este método es que la pequeña cantidad de cambio de una permutación a la siguiente permite implementar el método en un tiempo constante por permutación. Lo mismo también puede generar fácilmente el subconjunto de permutaciones pares, nuevamente en tiempo constante por permutación, omitiendo todas las demás permutaciones de salida.
Una alternativa a Steinhaus-Johnson-Trotter es el algoritmo de Heap, dicho por Robert Sedgewick en 1977 como el algoritmo más rápido para generar permutaciones en aplicaciones.
La siguiente figura muestra la salida de los tres algoritmos mencionados para generar todas las permutaciones de longitud $n=4$ , y de seis algoritmos adicionales descritos en la literatura.

Ordenación de todas las permutaciones de longitud $n=4$ generado por diferentes algoritmos. Las permutaciones son codificadas por colores, donde 1, 2, 3, 4.
Ordenación lexicográfica;
Steinhaus-Johnson-Trotter algoritmo;
El algoritmo de salto;
El algoritmo de transposición estelar de Ehrlich: en cada paso, la primera entrada de la permutación se intercambia con una entrada posterior;
El algoritmo de inversión prefijo de Zaks: en cada paso, se invierte un prefijo de la permutación actual para obtener la siguiente permutación;
El algoritmo de Sawada-Williams: cada permutación difiere de la anterior ya sea por un giro cíclico izquierdo por una posición, o un intercambio de las dos primeras entradas;
El algoritmo de Corbett: cada permutación difiere del anterior por un giro cíclico izquierdo de algún prefijo por una posición;
Ordenación única: cada columna es un cambio cíclico de las otras columnas;
Código gris de una sola pista: cada columna es un cambio cíclico de las otras columnas, más cualquier dos permutaciones consecutivas difieren sólo en una o dos transposiciones.
Permutaciones meándricas
Los sistemas meandricos dan lugar a permutaciones meandricas, un subconjunto especial de permutaciones alternativas. Una permutación alternativa del conjunto {1, 2,..., 2n} es una permutación cíclica (sin puntos fijos) tal que los dígitos en la notación cíclica se alternan entre números enteros pares e impares. Las permutaciones meándricas son útiles en el análisis de la estructura secundaria del ARN. No todas las permutaciones alternativas son meándricas. Se ha utilizado una modificación del algoritmo de Heap para generar todas las permutaciones alternativas de orden n (es decir, de longitud 2n) sin generar todas (2n)! permutaciones Es necesario generar estas permutaciones alternativas antes de analizarlas para determinar si son meándricas o no.
El algoritmo es recursivo. La siguiente tabla muestra un paso en el procedimiento. En el paso anterior, se generaron todas las permutaciones alternativas de longitud 5. Tres copias de cada uno de estos tienen un "6" se agrega al extremo derecho, y luego se aplica una transposición diferente que involucra esta última entrada y una entrada anterior en una posición par (incluida la identidad; es decir, sin transposición).
Juegos anteriores Transposición de dígitos Permutaciones supletorias
1-2-3-4-5-6 1-2-3-4-5-6
4, 6 1-2-3-6-5-4
2, 6 1-6-3-4-5-2
1-2-5-4-3-6 1-2-5-4-3-6
4, 6 1-2-5-6-3-4
2, 6 1-6-5-4-3-2
1-4-3-2-5-6 1-4-3-2-5-6
2, 6 1-4-3-6-5-2
4, 6 1-6-3-2-5-4
1-4-5-2-3-6 1-4-5-2-3-6
2, 6 1-4-5-6-3-2
4, 6 1-6-5-2-3-4
Aplicaciones
Las permutaciones se utilizan en el componente intercalador de los algoritmos de detección y corrección de errores, como los códigos turbo; por ejemplo, el estándar de telecomunicaciones móviles 3GPP Long Term Evolution utiliza estas ideas (consulte la especificación técnica 36.212 de 3GPP). Tales aplicaciones plantean la cuestión de la generación rápida de permutaciones que satisfagan ciertas propiedades deseables. Uno de los métodos se basa en los polinomios de permutación. También como base para un hash óptimo en Unique Permutation Hashing.

Diagrama de rotación para ${displaystyle sigma =(6,3,8,1,4,9,7,2,5)}$
^σ_i _i	1	2	3	4	5	6	7	8	9	Código Lehmer
1	×	×	×	×	×	•				d₉ = 5
2	×	×	•							d₈ = 2
3	×	×		×	×		×	•		d₇ = 5
4	•									d₆ = 0
5		×		•						d₅ = 1
6		×			×		×		•	d₄ = 3
7		×			×		•			d₃ = 2
8		•								d₂ = 0
9					•					d₁ = 0
Tabla de inversión	3	6	1	2	4	0	2	0	0

Juegos anteriores	Transposición de dígitos	Permutaciones supletorias
1-2-3-4-5-6		1-2-3-4-5-6
4, 6	1-2-3-6-5-4
2, 6	1-6-3-4-5-2
1-2-5-4-3-6		1-2-5-4-3-6
4, 6	1-2-5-6-3-4
2, 6	1-6-5-4-3-2
1-4-3-2-5-6		1-4-3-2-5-6
2, 6	1-4-3-6-5-2
4, 6	1-6-3-2-5-4
1-4-5-2-3-6		1-4-5-2-3-6
2, 6	1-4-5-6-3-2
4, 6	1-6-5-2-3-4

Contenido relacionado

Teorema de Gauss-Bonnet
En el campo matemático de la geometría diferencial, el teorema de Gauss-Bonnet es una fórmula fundamental que relaciona la curvatura de una superficie con...
Gerolamo Cardano
Teorema del buen orden
Más resultados...
Te puede interesar