Pruebas de referencia y análisis rápido de algoritmos de permutaciones

Decidí escribir esta pequeña reseña en inglés, con la esperanza de comenzar una nueva tendencia, que espero mejore la intercomunicación (¡No importa! Es solo una idea global de un joven kosmopolit).

Le insto a que responda esta publicación en inglés, incluso si tiene algunas dificultades con este idioma. No estoy escribiendo un poema en este momento y creo que podemos evitar la vergüenza sobre nuestras habilidades en inglés. Sin embargo, voy a hablar sobre algunos temas poéticos. - por supuesto, sobre la combinatoria y especialmente sobre la generación de objetos. Me refiero a permutaciones. Comencemos con las palabras con las que generalmente comienzan todos los cuentos de hadas: había una vez en Habrahabr (o he sido, no sé, tal vez fue) un manuscrito interesante sobre la generación de superpermutaciones. Ese tema pateó a algunos habrausers para escribir un código (ver comentarios) y a mí también. Y, de hecho, este evento me condujo nuevamente a un antiguo problema de algoritmos que se aceleran y prueban.

No soy lo suficientemente hábil en lenguaje matemático y fórmulas, por lo que ahora solo estoy imprimiendo tres algoritmos diferentes, codificados por mí en C89:

1. Algoritmo Johnson-Trotter
2. Algoritmo de Naryana
3. Algoritmo tomado de este habrpost , desarrollado por Mrrl (A. Astrelin)

Todos los algoritmos, mencionados anteriormente, no son recursivos.

Creo que mi versión del algoritmo Johnson-Trotter no es la mejor. Sin embargo, me apresuro a mostrarte los resultados que produce para n = 10.

Tiempo con salida de consola (significa printf)
real 1m19.410s
usuario 0m31.899s
sys 0m36.253s

Tiempo sin salida de consola
0m2.241s reales
usuario 0m2.236s
sys 0m0.004s

Mi versión del código Mrrl

Con salida de consola
real 1m11.565s
usuario 0m27.429s
sys 0m32.997s

Sin salida de consola
0m0.489s reales
usuario 0m0.486s
sys 0m0.002s

El último algoritmo similar a Naryana da tal resultado

Con salida de consola
real 1m10.223s
usuario 0m8.617s
sys 0m38.165s

Sin salida de consola
0m0.453s reales
usuario 0m0.449s
sys 0m0.004s

Gracias por leer Usé este sitio para la corrección ortográfica. Por supuesto, tiene el derecho absoluto de preguntarme, ¿dónde prometió el análisis rápido en el titular? En este momento no puedo dar una respuesta simple sobre qué algoritmo (¡ No se asuste! ¡Esta palabra es una palabra de esperanto normal !) Es más rápida. Tal vez estos tres scripts de código deberían ajustarse, si es posible, y probarse en varias situaciones. El primer y tercer algoritmo han sido codificados por mí después de un rápido vistazo al pseudocódigo (lectura de la descripción principalmente). El segundo algoritmo, si no me equivoco, es una versión estricta del algoritmo publicada anteriormente en Habrahabr.