[Bug-gsl] Slow gsl_permutation_valid()

[Rajeev Ayyagari]

Hello,

This is a suggestion rather than a bug report. The function
gsl_permutation_valid() in the current version (1.4) takes \Theta(1)
memory and runs in \Theta(n^2) time (where n is the size of the
permutation). It could be rewritten to use \Theta(n) memory and run in
\Theta(n) time. The time savings can be very significant if n is large (n
> 2000).

Here's an example of the faster implementation.

int myGslPermutationValid( gsl_permutation *p )
{
    int *watch = (int *) cmalloc(p -> size);

    for ( size_t i = 0; i < p -> size; i++ )
    {
        if ( p -> data[i] >= p -> size )
        {
            free( watch );
            return GSL_FAILURE;
        }

        if ( watch[p -> data[i]] )
        {
            free( watch );
            return GSL_FAILURE;
        }
        else
            watch[p -> data[i]] = 1;
    }

    free( watch );
    return GSL_SUCCESS;
}

Regards,
Rajeev.