(组合数学3.1.1.2)UVA 10098 Generating Fast(使用字典序思想产生所有序列)

/*
 * UVA_10098.cpp
 *
 *  Created on: 2013年10月8日
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

char s[11];
int l;

bool get() {
	int i = l - 1;
	int j;
	while (i > 0 && s[i - 1] >= s[i]) {
		--i;
	}
	if (!i) {
		return 0;
	}

	int mp = i;
	for (j = i + 1; j < l; ++j) {
		if (s[i - 1] >= s[j]) {
			continue;
		}

		if (s[mp] > s[j]) {
			mp = j;
		}
	}

	swap(s[mp], s[i - 1]);
	sort(s + i, s + l);
	return 1;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%s", s);
		l = strlen(s);

		sort(s, s + l);
		printf("%s
", s);

		while (get()) {
			printf("%s
", s);
		}
		printf("
");
	}

	return 0;
}