|
=={{header|C}}==
Just keep generating [[wp:Permutation#Systematic_generation_of_all_permutations|next lexicographic permutation]] until the last one; it's sorted by definition.
<lang c>#include <stdlib.h>
<lang c>#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int(*cmp_func)(const void*, const void*);
typedef struct pi *Permutations;
void perm_sort(void *a, int n, size_t msize, cmp_func _cmp)
/* Type of element on list to be sorted */
typedef const char *ElementType;
struct pi {
short list_size;
short *counts;
ElementType *crntperm;
};
Permutations PermutationIterator( ElementType *list, short listSize)
{
char *p, *q, *tmp = malloc(msize);
int ix;
# define A(i) ((char *)a + msize * (i))
Permutations p = malloc(sizeof(struct pi));
# define swap(a, b) {\
p->list_size = listSize;
memcpy(tmp, a, msize);\
p->counts = malloc( p->list_size * sizeof(short));
memcpy(a, b, msize);\
p->crntperm = malloc( p->list_size * sizeof(ElementType));
memcpy(b, tmp, msize); }
while (1) {
/* find largest k such that a[k - 1] < a[k] */
for (p = A(n - 1); (void*)p > a; p = q)
if (_cmp(q = p - msize, p) > 0)
break;
if ((void*)p <= a) break;
for (ix=0; ix<p->list_size; ix++) {
p->counts[ix] = ix;
p->crntperm[ix] = list[ix];
}
return p;
}
/* find largest l such that a[l] > a[k - 1] */
void FreePermutations( Permutations p)
for (p = A(n - 1); p > q; p-= msize)
{
if (NULL_cmp(q, ==p) p> 0) returnbreak;
free(p->crntperm);
free(p->counts);
free(p);
}
#define FREE_Permutations(pi) do {\
FreePermutations(pi); pi=NULL; } while(0)
swap(p, q); /* swap a[k - 1], a[l] */
ElementType *FirstPermutation(Permutations p)
/* flip a[k] through a[end] */
{
for (q += msize, p = A(n - 1); q < p; q += msize, p -= msize)
return p->crntperm;
swap(p, q);
}
free(tmp);
}
int scmp(const void *a, const void *b) { return strcmp(*(char**)a, *(char**)b); }
ElementType *NextPermutation( Permutations p)
{
int ix, j;
ElementType *crntp, t;
int main()
crntp = p->crntperm;
ix = 1;
do {
t = crntp[0];
for(j=0; j<ix; j++) crntp[j] = crntp[j+1];
crntp[ix] = t;
if (p->counts[ix] > 0) break;
ix += 1;
} while (ix < p->list_size);
if (ix == p->list_size) return NULL;
p->counts[ix] -= 1;
while(--ix) {
p->counts[ix] = ix;
}
return crntp;
}
/* Checks to see if list is ordered */
int isInOrder(ElementType *letrList, int size )
{
int ji;
char *strs[] = { "spqr", "abc", "giant squid", "stuff", "def" };
ElementType *p0 = letrList, *p1 = letrList+1;
perm_sort(strs, 5, sizeof(char*), scmp);
for (j= 1; j<size; j++) {
if ( strcmp( *p0, *p1) > 0) break; /* compare strings */
// if ( *p0 > *p1) break; /* compare numeric values */
p0++, p1++;
}
return ( j == size );
}
int main( )
{
short size =5;
ElementType *prm;
ElementType mx[] = {"another", "sorted", "to_be", "list", "here's" };
Permutations pi = PermutationIterator(mx, size);
for ( prm = FirstPermutation(pi); prm; prm = NextPermutation(pi))
if (isInOrder( prm, size) ) break;
if (prm) {
int j;
printf("Sorted: ");
for (j=0; j<size; j++)
printf("%s ",prm[j]);
printf("\n");
}
for (i = 0; i < 5; i++)
FreePermutations( pi);
printf("%s\n", strs[i]);
return 0;
return 0;
}</lang>
| 