POJ 1256 Anagram 解题报告

一、   问题描述

题目：

题目大意

    输入一个包含n（n<=13）个字符的字符串，按字典顺序输出这n个字符的所有的排列，不能有相同的排列。

    注意：'A'<'a'<'B'<'b'<...<'Z'<'z'.

Sample Input

3

aAb

abc

acba

Sample Output

Aab

Aba

aAb

abA

bAa

baA

abc

acb

bac

bca

cab

cba

aabc

aacb

abac

abca

acab

acba

baac

baca

bcaa

caab

caba

cbaa

二、解题思路

先将输入的n个字符按从小到大进行排序。然后使用回溯法，从头到尾进行选择每一个没有使用过的字符。进行到最后一层时输出字符串。

为了消除重复的排列，在回溯后检查后面一个字符是否和前面的相同，如果相同则一直跳到后面第一个不相同的字符。

三、代码

 

#include<iostream>
#include <algorithm>
#include<string>
using namespace std;
char str[15];    //存储输入字符串
char out[15];    //存储输出字符串
bool b[15];        //字符是否已经使用
int N;            //字符个数
//比较两个字符的大小
int cmp(const void * a,const void *b)
{
    char c=*(char *)a;
    char d=*(char *)b;
    if(c>=97)
    {
        c-=32;
        if(d>=97)
        {
            d-=32;
            return c-d;
        }
        else
        {
            if(c==d)
                return 1;
            else
                return c-d;
        }
    }
    else
    {
        if(d>=97)
        {
            d-=32;
            if(c == d)
                return -1;
            else
                return c-d;
        }
        return c-d;
    }
}
//回溯
void backtrace(int n)
{
    if(n==N)//最后一层，输出字符串
    {
        printf("%s\n",out);
    }
    for(int i=0;i<N;++i)
    {
        if(b[i]==false )
        {
            out[n]=str[i];
            b[i]=true;
            backtrace(n+1);
            b[i]=false;
            int k=i+1;
            //跳到第一个不相同的字符
            while(k<N && str[k]==str[i] )
                k++;
            k--;//循环结束时i会自增，先减1
            i=k;
        }
    }
}
int main()
{
    int t,T;
    scanf("%d",&T);
    for(t=0;t<T;++t)
    {
        cin>>str;
        N=strlen(str);
        memset(b,0,sizeof(b));
        out[N]='\0';
        //对输入字符进行排序
        qsort(str,N,sizeof(str[0]),cmp);
        backtrace(0);
    }
    return 0;
}