[Shootout-list] fannkuch.c

[Brent Fulgham]

Applied, thanks.

--- Falk Hueffner <falk@debian.org> wrote:
> Hi,
> 
> apparently it got lost last time; here's a C version
> of fannkuch.
> 
> -- 
> 	Falk
> > #include <stdbool.h>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> 
> static inline void swap(int *i, int *j) {
>     int tmp = *i;
>     *i = *j;
>     *j = tmp;
> }
> 
> static inline void reverse(int *first, int *last) {
>     while (first < last)
>         swap(first++, --last);
> }
> 
> static bool next_permutation(int *first, int *last)
> {
>     int *i = last - 1;
>     while (true) {
>         int *ii = i;
>         i--;
>         if (*i < *ii) {
>             int *j = last;
>             while (*i >= *--j)
>                 ;
>             swap(i, j);
>             reverse(ii, last);
>             return true;
>         }
>         if (i == first) {
>             reverse(first, last);
>             return false;
>         }
>     }
> }
> 
> static int count_reversals(const int *pin, int n) {
>     int p[n];
>     int count = 0;
>     memcpy(p, pin, sizeof p);
>     while (p[0] != 1) {
> 	reverse(p, p + p[0]);
> 	count++;
>     }
>     return count;    
> }
> 
> int main(int argc, char *argv[]) {
>     int n = atoi(argv[1]);
>     int p[n], i;
>     for (i = 0; i < n; i++)
> 	p[i] = i + 1;
> 
>     int max_count = 0;
>     do {
> 	int count = count_reversals(p, n);
> 	if (count > max_count)
> 	    max_count = count;
>     } while (next_permutation(p, p + n));
>     printf("%d\n", max_count);
> 
>     return 0;
> }
>