# 【UVa】195. Anagram

## [題目連結](https://vjudge.net/problem/UVA-195)

## **時間複雜度**

* $O(N$ x $N!)$

## **解題想法**

這題其實沒有很難處理，但是我當時再寫的時候是自己手刻一個 next_permutation 出來，說實話這樣不是很有意義 QQ 甚至有些浪費時間，因為寫出來的東西速度比不上官方的函式庫所以吃滿了 <span style="color:orange">**TLE**</span>，但之後我改成用 STL 的 next_permutation 就可以過了

## **完整程式**

這題比較需要注意的是他的字典敘事要自己自定的，但簡單寫一個 cmp 出來就可以解決了

### next_permutation 解

/* Question : UVa 195. Anagram */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x) memset(x, 0x3F, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 10 + 50;
const int Mod = 1e9 + 7;
int n, len;
string str;

bool compare( char a, char b ){
    char aa = toupper(a), bb = toupper(b);
	if( aa == bb ) return a < b;
	else return aa < bb;
}

signed main(){
    opt;
    cin >> n;
    for( int i = 0 ; i < n ; i++ ){
        cin >> str;
        sort(str.begin(), str.end(), compare);
        // cout << str;
        len = str.size();
        do{
            cout << str << "\n";
        }while( next_permutation(str.begin(), str.end(), compare) );
    }
}

### 手刻解

雖然速度比較慢，但是結果應該是對的

/* Theoretically AC Answer */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x) memset(x, 0x3F, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 10 + 50;
const int Mod = 1e9 + 7;
int n, len;
string str;

bool compare( char a, char b ){
    char aa = toupper(a), bb = toupper(b);
	if( aa == bb ) return a < b;
	else return aa < bb;
}

void reverseArray( int begin, int end ){
    int dif = end - begin;
    for( int i = 0 ; i < dif / 2 + 1 ; i++ ) swap( str[begin+i], str[end-i] );
}

bool nextPermutation(){
    int p = len - 1; // p stands for Partition Number
    while( p > 0 && compare(str[p], str[p-1]) ) p--;
    p--;

    if( p == -1 ) return false;

    int c = len - 1; // c stands for Change Number
    while( compare(str[c], str[p]) ) c--;

    swap(str[c], str[p]);
    reverseArray(p+1, len-1);
    return true;
}   

signed main(){
    opt;
    cin >> n;
    for( int i = 0 ; i < n ; i++ ){
        cin >> str;
        sort(str.begin(), str.end(), compare);
        // cout << str;
        len = str.size();
        do{
            cout << str << "\n";
        }while( nextPermutation() );
    }
}