Contar el Número de Secuencias

Question

La pregunta es:
Dada una secuencia de enteros positivos A={1,2,3,...,N}.
Contar el número de secuencias que se pueden obtener después de hacer K swaps entre los elemento para un determinado N ?
Mi planteamiento:
Mi algoritmo para resolver este tipo de programación es muy ingenuo. Yo sólo podía pensar en la fabricación de todos los posibles k swaps y, a continuación, el recuento de las secuencias.
Alguien me puede ayudar con un mejor algoritmo?

Answer 1

Voy a asumir que usted quiere decir que el $K$ swaps son adyacentes entre coordina y lleva a cabo en secuencia y no necesariamente disjuntos. Por ejemplo, comenzando con $(1,2,\ldots,N)$, el primer intercambio podría ser el intercambio de las 2ª y 3ª de coordenadas, la segunda de intercambio podría ser el intercambio de las 4 y 5 de coordenadas, y la tercera de intercambio podría intercambio de la 3ª y la 4ª de coordenadas. Por lo tanto, los swaps son entre elementos adyacentes, como usted requiere, pero las coordenadas no son necesariamente disjuntos, y el orden en que estos intercambios se llevan a cabo es importante. Puesto que usted está mirando para todas las secuencias que se pueden obtener, a partir de la secuencia de $(1,2,\ldots,N)$, utilizando exactamente $K$ adyacente swaps, en realidad estás buscando el número de vértices que puede ser alcanzado en la ordenación de burbuja gráfico de $BS(N)$, a partir de cualquier particular vértice, el uso de un pie de longitud exactamente $K$. El gráfico de $BS(N)$ es el grafo de Cayley del grupo simétrico $S_n$ generado por el conjunto de $n-1$ adyacente transposiciones $\{(1,2),(2,3),\ldots,(n-1,n)\}$. No sé si alguna fórmula para que esta función se $f(N,K)$ es conocido. Puedes realizar algunas simulaciones (el uso de paquetes de software tales como GAP o SAGE, que se han incorporado en las funciones para la construcción de Cayley gráficos y el cálculo de distancias entre vértices) y determinar si los valores obtenidos son en OEIS.

Answer 2

Sugerencia: Por $K$ adyacente swaps supongo que te refieres a que elija una carrera de $2K$ números y de intercambio de cada par. Así que si $K=3$ nos podría terminar con $\{1,2,4,3,6,5,8,7,9,10\dots,N\}$ por ejemplo. Si es así, el resultado se determina por el primer número, no importa el fin de realizar los intercambios.