Pages

Thursday, December 4, 2014

Get next Permutation - C program

Rule:

1. Find largest index i such that array[i − 1] < array[i].
2. Find largest index j such that j ≥ i and array[j] > array[i − 1].
3. Swap array[j] and array[i − 1].
4. Reverse the suffix starting at array[i].

Code:
#include "stdio.h"

#define MAX 100

void ins_sort(int *a, int n) {
    int i, j, tmp;

    for (i = 1; i < n; i++) {
        for (j = i; j > 0; j--) {
            if (a[j] < a[j-1]) {
                tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
            }
        }
    }
}

void reverse(int *begin, int *end) {
    int tmp;
    while (begin < end) {
        tmp = *begin;
        *begin = *end;
        *end = tmp;
        begin++;
        end--;
    }
}

int next_permutation(int *begin, int *end)
{
    int tmp;
    int *i, *j, *k;

    if (begin == end)
        return 0;

    /* Single element */
    i = begin;
    ++i;
    if (i == end)
        return 0;

    i = end;
    --i;

    while (1)
    {
        j = i;
        --i;

        if (*i < *j)
        {
            k = end;

            while (!(*i < *--k));

            //swap(i, k);
            tmp = *i;
            *i = *k;
            *k = tmp;

            reverse(j, --end);
            return 1;
        }

        if (i == begin)
        {
            reverse(begin, --end);
            return 0;
        }
    }
}

int main() {
    int n, a[MAX], i;

    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    ins_sort(a, n);

    while (next_permutation(a, a+n)) {
        for (i = 0; i < n; i++)
            printf("%d ", a[i]);
        printf("\n");
    }
    return 0;
}