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).

image 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:

  1. Johnson-Trotter algorithm
  2. Naryana algorithm
  3. 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.

Комментарии (8)


  1. cry_san
    14.12.2018 06:21

    Копипаст?


    1. dcc0 Автор
      14.12.2018 14:17

      В смысле?


    1. dcc0 Автор
      14.12.2018 15:23

      Sorry, (I have violated my own rules ). What do you mean, asking about copy and paste?


  1. nerudo
    14.12.2018 08:16
    +1

    С сожалением отмечаю, что основная задача англоязычных статей на хабре (чтобы соответствовать новым трендам) — быть написанными на английском. А уж что там внутри содержится — ставится в третью очередь.


  1. altrus
    14.12.2018 08:20

    this is one huggin' informative article


  1. neurocore
    14.12.2018 11:47

    Недавно решал подобную задачу, но на доске 3x3. В целом алгоритм крайне прост — в каждой позиции есть 1 или 3 хода, поиск в глубину решает её за миллисекунды.


    1. mwambanatanga
      14.12.2018 15:27

      Почему "1 или 3"? Если не считать ходов назад, то из угла один выход, с ребра — два, а из остальных точек — три. Или я недопонял что-то очень важное?


      1. neurocore
        14.12.2018 15:28

        А, ну да, ещё 2