I decided to write this small review in English, hoping to start a new trend, which I expect will improve intercommunication (Don't mind! It is just globalistic idea of a young kosmopolit).
I urge you to reply this post in English, even you have some difficulties with this language. I am not writing a poem right now and I think we can avoid embarrassment about our English skills. However I am going to talk about some poetical issues — of course, about combinatorics and especially about generating objects. I mean permutations. Let's start with the words with those all the fairytales are usually started: once upon a time on Habrahabr had been (or have been, I don't know, maybe was) published an interesting manuscript about generating superpermutations. That topic kicked some habrausers up to write some code (see comments ) and me too. And actually this event led me again to an ancient problem of algorithms speeding up and testing.
I am not skilled enough in mathematical language and formulas, so I am just printing three different algorithms now, coded by me in C89:
All algorithms, mentioned above, are not recursive.
My version of Johnson-Trotter algorithm is not the best, I think. Nevertheless I hurry up to show you the resuts it produces for n=10.
Time with console output (means printf)
real 1m19.410s
user 0m31.899s
sys 0m36.253s
Time without console output
real 0m2.241s
user 0m2.236s
sys 0m0.004s
My verstion of Mrrl code
With console output
real 1m11.565s
user 0m27.429s
sys 0m32.997s
Without console output
real 0m0.489s
user 0m0.486s
sys 0m0.002s
The last Naryana like algorithm gives such result
With console output
real 1m10.223s
user 0m8.617s
sys 0m38.165s
Without console output
real 0m0.453s
user 0m0.449s
sys 0m0.004s
Thanks for reading. I used this site for spell checking. Of course, you have an absolute right to ask me, where the quick analysis promised in the headline?! At this moment I can't give a simple answer about which algoritmo (Don't panic! This word is a normal Esperanto word! ) is faster. Maybe these three code-scripts should be tuned, if it is possible, and tested in a number of situations. First and third algorithms has been coded by me after a quick look at pseudocode (reading description mostly). The second algorithm, if If I'm not mistaken, is a strict version of algorithm published earlier on Habrahabr.
I urge you to reply this post in English, even you have some difficulties with this language. I am not writing a poem right now and I think we can avoid embarrassment about our English skills. However I am going to talk about some poetical issues — of course, about combinatorics and especially about generating objects. I mean permutations. Let's start with the words with those all the fairytales are usually started: once upon a time on Habrahabr had been (or have been, I don't know, maybe was) published an interesting manuscript about generating superpermutations. That topic kicked some habrausers up to write some code (see comments ) and me too. And actually this event led me again to an ancient problem of algorithms speeding up and testing. I am not skilled enough in mathematical language and formulas, so I am just printing three different algorithms now, coded by me in C89:
- Johnson-Trotter algorithm
- Naryana algorithm
- Algorithm taken from this habrpost, developed by Mrrl (A. Astrelin)
All algorithms, mentioned above, are not recursive.
My version of Johnson-Trotter algorithm is not the best, I think. Nevertheless I hurry up to show you the resuts it produces for n=10.
Time with console output (means printf)
real 1m19.410s
user 0m31.899s
sys 0m36.253s
Time without console output
real 0m2.241s
user 0m2.236s
sys 0m0.004s
My verstion of Mrrl code
With console output
real 1m11.565s
user 0m27.429s
sys 0m32.997s
Without console output
real 0m0.489s
user 0m0.486s
sys 0m0.002s
The last Naryana like algorithm gives such result
With console output
real 1m10.223s
user 0m8.617s
sys 0m38.165s
Without console output
real 0m0.453s
user 0m0.449s
sys 0m0.004s
Thanks for reading. I used this site for spell checking. Of course, you have an absolute right to ask me, where the quick analysis promised in the headline?! At this moment I can't give a simple answer about which algoritmo (Don't panic! This word is a normal Esperanto word! ) is faster. Maybe these three code-scripts should be tuned, if it is possible, and tested in a number of situations. First and third algorithms has been coded by me after a quick look at pseudocode (reading description mostly). The second algorithm, if If I'm not mistaken, is a strict version of algorithm published earlier on Habrahabr.
