I came back home, without a laptop. With one hand holding the Algorithms book (I really recommend that one) and with notebook and a pen in the other. I choose notebook and pen. It did the trick.
I know I masturbate on that issue, but it's fun. After some furious paper programming I got here:
I asked myself 3 questions at the beginning:
- How many times "1" will be first?
- How many times "4" will be in the result?
- How many times "5" will be in the result?"
I wanted to answer that questions without the use of any offset indexes kept in memory in other array. Keep it simple: what do I know about my input data?
So my answers were like that:
- If I take all the sizes of following tables and multiply them, I'll get 12.
- Always, cause it's a single element array, so 36 (total possible permutations.
- The same as answer number one. 6 times in cycle of 3, 18.
The main conclusion was that I can fill the results array column by column instead of row by row. All permutations will be fully calculated at once, at the very end. No gathering the permutation by permutation and then pushing it to the results. No no no, that needs indexes and traveling across the array many times. This idea dropped the complexity from O(n^3) to O(n).
Cycles, subcycles, offsets. The most important thing was to calculate a proper index in the result table and stick the current argument element exactly there (IBID). No more talk, code is below and benchmark is on the gist comment.
