Re: [Help-gsl] gsl_permutation_next

[Regis Smith]

I think Pavel Sinitcyn's code gives a more literal translation of step L3 in
Knuth's description of the algorithm ("Algorithm L" in AoCP vol 4, page 319).
The change decreases the running time by over 10% in my tests.  I haven't
tested for accuracy, though.

Incidentally, the existing version of gsl_permutation_next() in permutatiion.c
has a superfluous check in the boolean expression on line 155:

    (p->data[j] > p->data[i]) && (p->data[j] < p->data[k])

The while loop starting on line 141 guarantees that p->data[j] < p->data[k] for
i<k<j (Knuth explains this in step L3).  But I think the slow down is caused by
the structure of the for loop, which seems awkward compared to the
straightforward textbook version.

Regis

On Wed, Apr 12, 2017 at 11:44:07AM +0200, Patrick Alken wrote:
> Hello, thanks for working on this. I will take a look at your function
> and do some testing and get back to you
> 
> On 04/11/2017 05:58 PM, Pavel Sinitcyn wrote:
> > Hello everyone,
> >
> > I was reading the permutation module of GSL and found that a function
> > "gsl_permutation_next" can be improved (you can see function
> > gsl_permutation_next0
> > <https://gist.github.com/pgsin/fc779f7ce7d4724221fe2dc5450e9358#file-gsl_permutation_next-test-c-L111>,
> > more specifically - this line
> > <https://gist.github.com/pgsin/fc779f7ce7d4724221fe2dc5450e9358#file-gsl_permutation_next-test-c-L135>
> > ).
> >
> > I made a benchmarking on my computer (AMD Opteron(TM) Processor 6276; gcc
> > -O2; gcc Ubuntu 4.8.4-2ubuntu1~14.04.3) and found a significant difference
> > in the performance (result contains stdout; bencmark.pdf - visualisation).
> >
> > Best,
> > Pavel Sinitcyn
> 
> 
>