问题描述

输入一个整数，如何实现其全排列。

具体地说，就是输入一个正整数，目前限定为n为1到10之间。全排列指
如果输入3，则输出123，132，213，231，312，321。
如何实现？假如输入9，则有9×8×7×6×5×4×3×2种情况。

解决方案

 #include<iostream>
using namespace std;
void Permutation(char* pStr, char* pBegin);   

void permutation(char* pStr)
{
      Permutation(pStr, pStr);
}  

void Permutation(char* pStr, char* pBegin)
{
    if(!pStr || !pBegin)
        return;  

    if(*pBegin == '')
    {
        printf("%sn", pStr);
    }
    else
    {
        for(char* pCh = pBegin; *pCh != ''; ++ pCh)
        {
            // swap pCh and pBegin
            char temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;  

            Permutation(pStr, pBegin + 1);
            // restore pCh and pBegin
            temp = *pCh;
            *pCh = *pBegin;
            *pBegin = temp;
        }
    }
} 

int main()
{
    char str[] ={'1','2','3',''};
    permutation(str);
    getchar();
    return 0;
}

在线运行：

http://codepad.org/pTA0yiRn

123
132
213
231
321
312

解决方案二：

就是1—n，n个数经行排列组合。for循环n次，每次依次选一个数，选过的数不能再选。

解决方案三：

自己来，比起一楼的方法无疑更麻烦一点。

```public class 全排列 {

public static String[] strs;
public static String str;
public static Random rand;

public static void main(String[] args) {
Set set = totalRank(9);
for (String rank : set) {
System.out.println(rank);
}
// System.out.println();
}

public static Set totalRank(int n) {
    str = genereatString(n);
    Set<String> set = new HashSet<String>();
    do {
        if (set.contains(str)) {
            str = genereatString(n);
        } else {
            set.add(str);
        }
    } while (set.size() != calFactorial(n));
    return set;
}

//计算阶乘
public static int calFactorial(int n) {
    int sum = 1;
    for (int i = 1; i <= n; i++) {
        sum *= i;
    }
    return sum;
}

/**
 * 生成一个数组包含"1"，"2"，"3"，"4"，"5" 5个字符串
 */
public static String[] generatearr(int n) {
    String[] strs = new String[n];
    for (int i = 0; i < n; i++) {
        strs[i] = "" + (i + 1);
    }
    return strs;
}
/**
 * 生成一个排列 ，每次随机取一个整数（0，1，2，3，4）取过了的就不再取，
 直到取到5个。每一个数字代表一个字符串数组中的字符串。
 */
public static String genereatString(int n) {
    strs = generatearr(n);
    rand = new Random();
    String s = "";
    Set nums = new HashSet();
    Integer a1;
    for (int i = 0; i < n;) {
        a1 = rand.nextInt(n);
        if (nums.contains(a1)) {
            a1 = rand.nextInt(n);
        } else {
            s += strs[a1];
            nums.add(a1);
            i++;
        }
    }
    return s;
}

}```

当n=9时，运行了半分钟才出来结果。如果这种算法可行，那么如何去优化呢？总感觉效率不够高。