[Shootout-list] fannkuch.c

[Falk Hueffner]

--=-=-=

Hi,

apparently it got lost last time; here's a C version of fannkuch.

-- 
	Falk

--=-=-=
Content-Type: text/x-csrc
Content-Disposition: inline; filename=fannkuch.c

#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;
}

--=-=-=--