http://poj.org/problem?id=1833
按照字典的顺序（a-z) (1-9），可以得出任意两个数字串的大小。比如“123”， 最小的是“123”（从小到大），最大的是“321”(从大到小)。这样对于“123”的所有排列，可以得到按照字典序排序的有序集合 : 1 2 3 ， 1 3 2 ， 2 1 3 ， 2 3 1 ， 3 1 2 ， 3 2 1。
如果有n个数的排列，
1) 从最右边开始找，找到第一个 i ，使得arr[i] > arr[i-1];
2) 从 i 到 n 这个范围找到最小的比 arr[i-1] 大的数字，交换这个数和 arr[i-1];
3) 从 arr[i] 到 arr[n] 排序 qsort(arr, i, n);
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#define N_MAX 1025
int n, k;
int a[N_MAX]; void printf_arr()
{
for (int i = ; i <= n; i++) {
printf("%d ", a[i]);
}
printf("\n");
} void qsort(int *a, int begin, int end)
{
if (begin >= end) return;
int l = begin, r = end, k = a[l];
while (l != r) {
while (l < r && k <= a[r]) r--;
while (l < r && k >= a[l]) l++;
if (l < r) {
int tmp = a[l];
a[l] = a[r];
a[r] = tmp;
}
}
a[begin] = a[l];
a[l] = k;
qsort(a, begin, l - );
qsort(a, l + , end);
} int main(int argc, char* argv[])
{
//setbuf(stdout, NULL);
//freopen("sample_input.txt", "r", stdin); int T = ;
scanf("%d", &T); while (T--) {
scanf("%d %d", &n, &k); for (int j = ; j <= n; j++) {
scanf("%d", &a[j]);
} while (k--) {
int i = n;
// step 1 : find a[i] > a[i - 1]
for (; i > ; i--) {
if (a[i] > a[i - ])
break;
}
// the biggest
if (i == ) {
for (int i = ; i <= n; i++) {
a[i] = i;
}
continue;
} // step 2 : find the min in [i, n]
int min = n;
int l = i - ;
int r = i;
for (int j = i; j <= n; j++) {
if (a[j] > a[l] && a[j] < min) {
min = a[j];
r = j;
}
} // step 2 : swap(min, a[i - 1])
int tmp = a[l];
a[l] = a[r];
a[r] = tmp; // step 3 : qsort [i, n]
qsort(a, i, n);
} printf_arr();
}
return ;
}