Teste de benchmark e análise rápida de algoritmos de permutações

Decidi escrever esta pequena resenha em inglês, na esperança de iniciar uma nova tendência, que, espero, melhore a intercomunicação (não se importe! É apenas uma idéia globalista de um jovem kosmopolit).

Peço que você responda este post em inglês, mesmo que você tenha algumas dificuldades com esse idioma. Não estou escrevendo um poema no momento e acho que podemos evitar vergonha sobre nossas habilidades em inglês. No entanto, eu vou falar sobre algumas questões poéticas - é claro, sobre combinatória e especialmente sobre a geração de objetos. Quero dizer permutações. Vamos começar com as palavras com aquelas em que todos os contos de fadas costumam ser iniciados: era uma vez em que Habrahabr havia sido (ou, sei lá, talvez tenha sido) publicado um manuscrito interessante sobre a geração de superpermutações. Esse tópico levou alguns habrausers a escrever algum código (ver comentários) e eu também. E, na verdade, esse evento me levou novamente a um antigo problema de algoritmos acelerando e testando.

Como não tenho experiência suficiente em linguagem matemática e fórmulas, estou imprimindo agora três algoritmos diferentes, codificados por mim no C89:

1. Algoritmo Johnson-Trotter
2. Algoritmo Naryana
3. Algoritmo retirado deste habrpost , desenvolvido por Mrrl (A. Astrelin)

Todos os algoritmos, mencionados acima, não são recursivos.

Minha versão do algoritmo Johnson-Trotter não é a melhor, eu acho. No entanto, corro para mostrar os resultados que produz para n = 10.

Tempo com a saída do console (significa printf)
1m19.410s reais
usuário 0m31.899s
sys 0m36.253s

Tempo sem saída do console
0m2.241s reais
usuário 0m2.236s
sys 0m0.004s

Minha versão do código Mrrl

Com saída do console
real 1m11.565s
usuário 0m27.429s
sys 0m32.997s

Sem saída do console
0m0.489s reais
usuário 0m0.486s
sys 0m0.002s

O último algoritmo de Naryana dá esse resultado

Com saída do console
1m10.223s reais
usuário 0m8.617s
sys 0m38.165s

Sem saída do console
0m0.453s reais
usuário 0m0.449s
sys 0m0.004s

Obrigado pela leitura. Eu usei este site para verificação ortográfica. Claro, você tem o direito absoluto de me perguntar, onde a análise rápida prometeu na manchete ?! No momento, não posso dar uma resposta simples sobre qual algoritmo ( Não entre em pânico! Esta palavra é uma palavra normal do esperanto !) É mais rápido. Talvez esses três scripts de código devam ser ajustados, se possível, e testados em várias situações. O primeiro e o terceiro algoritmos foram codificados por mim depois de uma rápida olhada no pseudocódigo (principalmente na descrição da leitura). O segundo algoritmo, se não me engano, é uma versão estrita do algoritmo publicada anteriormente no Habrahabr.