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;
ins_sort(a, n);
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;
}