学步园

//本题主要思想是递归，Rank(T data[],int start,int end)的意义是data数组在start以前的部分原样输出，

//start到结束的部分求全排列，data中允许有重复字符

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
void Swap(T &var1,T &var2)
{
    T tmp;
    tmp=var1;
    var1=var2;
    var2=tmp;
}

template <typename T>
void Rank(T data[],int start,int end)

{

//当只需要将最后一个元素求全排列时，则将当时的数组输出即可
    if(start == end)
    {
        for(int i=0;i<=end;i++)
            cout<<data[i];
        cout<<endl;
        return;
    }

    for(int i=start;i<=end;i++)

    {
        int flag=0;//标记当前的交换和递归是否要进行
        for(int j=start;j<i;j++)

        {

//如果要交换的元素i和第一个元素start之间有和要交换的元素相等的元素j

//则这一次交换个递归不执行，因为若执行则得到和交互start和j相同的结果

            if(data[i]==data[j])
            {
                flag=1;
                break;
            }
        }
        if(flag!=1)
        {

//保证要求全排列的start开始的子串的第一个位置要每个字符都出现一边

            Swap(*(data+i),*(data+start));

//子串第一个位置不动，全排列后边的串
            Rank(data,start+1,end);
            Swap(*(data+start),*(data+i));
        }
    }
    return;
}

int main()
{
    cout<<"input the size of the array:"<<endl;
    int n;
    char array[20];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>array[i];
    Rank(array,0,n-1);
    return 1;
}