排列问题

全排列

所谓全排列，就是打印出字符串中所有字符的所有排列。例如输入字符串abc，则打印出 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba 。

一般最先想到的方法是暴力循环法，即对于每一位，遍历集合中可能的元素，如果在这一位之前出现过了该元素，跳过该元素。例如对于abc，第一位可以是 a 或 b 或 c 。当第一位为 a 时，第二位再遍历集合，发现 a 不行，因为前面已经出现 a 了，而 b 和 c 可以。当第二位为 b 时 ， 再遍历集合，发现 a 和 b 都不行，c 可以。可以用递归或循环来实现，但是复杂度为  。有没有更优雅的解法呢。

首先考虑bac和cba这二个字符串是如何得出的。显然这二个都是abc中的 a 与后面两字符交换得到的。然后可以将abc的第二个字符和第三个字符交换得到acb。同理可以根据bac和cba来得bca和cab。（非字典序）

因此可以知道 全排列就是从第一个数字起每个数分别与它后面的数字交换，也可以得出这种解法每次得到的结果都是正确结果，所以复杂度为 O(n!)。找到这个规律后，递归的代码就很容易写出来了：

#include 
  
    #include 
   
     //交换两个字符 void Swap(char *a ,char *b) { char temp = *a; *a = *b; *b = temp; } //递归全排列，start 为全排列开始的下标， length 为str数组的长度 void AllRange(char* str,int start,int length) { if(start == length-1) { printf("%s\n",str); } else { for(int i=start;i<=length-1;i++) { //从下标为start的数开始，分别与它后面的数字交换 Swap(&str[start],&str[i]); AllRange(str,start+1,length); Swap(&str[start],&str[i]); } } } void Permutation(char* str) { if(str == NULL) return; AllRange(str,0,strlen(str)); } void main() { char str[] = "abc"; Permutation(str); } 
    
  

/ * 求N个元素的全排列 */ public class Main { private static int count = 0; public static void main(String[] args) { char[] data = "abc".toCharArray(); f(data, 0); System.out.println("一共有" + count + "排列"); } / * 取第一个元素，把剩下的这些进行递归处理 * 取第二个元素，把剩下的这些进行递归处理 * ..... * ..... * 当前所关注的元素，每次都不同，应该写进递归中 * * @param data * @param k 当前的交换位置（关注点），与其后的元素交换 */ public static void f(char[] data, int k) { //递归终止条件 //base case if (k == data.length - 1) {//打印 我在data.length-1 打印 也就是最后一个 在data.length 打印也可以 只是对循环了一次 count++; for (int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } System.out.println(); } for (int i = k; i < data.length; i++) { { char t = data[k]; data[k] = data[i]; data[i] = t; }//试探 f(data, k + 1); { char t = data[k]; data[k] = data[i]; data[i] = t; }//回溯 !递归结束后一定要把它换回来 //比如有几个开关串联 点灯不亮 我要把它打开 //一、先假设有一个开关没开，当我把一个开关试探完后，在试探下一个之前，我一定要把前一个开关复原。 //假设两个 //...... } } }

 还可以用选数字的方式产生排列数

public class Main { private static final int n = 3;//0~(n-1) 的全排列 private static int count = 0; private static int arr[] = new int[n];//用于输出选的数字 private static int flag[] = new int[n];//用于标记是否已选择 public static void main(String[] args) { f(0); System.out.println(count); } static void f(int k) { if (k == arr.length) { for(int i = 0; i < arr.length; i++){ System.out.print(arr[i]+" "); }System.out.println(); count++; return; } for (int i = 0; i < arr.length; i++) { if (flag[i] == 0) {//选了的就不选了 flag[i] = 1;//标记为 已经选了 arr[k] = i;// 重那个数开始 + 响应的数字即可 f(k + 1); flag[i] = 0;//回溯 } } } } 

 去掉 flag 数组，可以选出重复的数字

public class Main { private static final int n = 3;//0~(n-1) 的全排列 private static int count = 0; private static int arr[] = new int[n];//用于输出选的数字 public static void main(String[] args) { f(0); System.out.println(count); } static void f(int k) { if (k == arr.length) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); count++; return; } for (int i = 0; i < arr.length; i++) { arr[k] = i; f(k + 1); } } }

 注：输出的顺序并不是字典序。

字典序排列的全排列 

如何按照大小顺序输出一个数字序列的全排列

#include 
  
    #include 
   
     #include 
    
      using namespace std; bool getBrother(string &dest){ if (dest.size() <= 1) { return false; } int before = dest.size() - 2; int after = dest.size() - 1; if (dest[after] > dest[before]){ swap(dest[after], dest[before]); return true; } char min = '9'; int pos; while ((--before) >= 0){ pos = 0;//每次循环记得要把pos复位 for (int i = after; i > before; i--){ if (dest[i] > dest[before] && dest[i] < min){ min = dest[i]; pos = i; } } if (pos > before){ swap(dest[pos], dest[before]); sort(&dest[before + 1], &dest[after + 1]);//从开始元素到待排序元素的下一个位置 return true; } } return false; } void allRank(string &dest){ if (dest.size() <= 1) { return; } sort(&dest[0], &dest[dest.size()]); do { cout << dest << endl; } while (getBrother(dest)); } int main(){ string s("123"); allRank(s); return 0; } 
     
    
  

选数字 

public class Main { private static final int n = 4;//1~n 的全排列 private static int count = 0; private static int arr[] = new int[n];//用于输出选的数字 private static int flag[] = new int[n];//用于标记是否已选择 public static void main(String[] args) { f(0); System.out.println(count); } static void f(int k) { if (k == arr.length) { for(int i = 0; i < arr.length; i++){ System.out.print(arr[i]+" "); }System.out.println(); count++; return; } for (int i = 0; i < arr.length; i++) { if (flag[i] == 0) {//选了的就不选了 flag[i] = 1;//标记为 已经选了 arr[k] = i+1;//不要0 f(k + 1); flag[i] = 0;//回溯 } } } } 

去重的全排列 

为了得到不一样的排列，可能我们最先想到的方法是当遇到和自己相同的就不交换了。如果我们输入的是abb，那么第一个字符与后面的交换后得到 bab、bba。然后abb中，第二个字符和第三个就不用交换了。但是对于bab，它的第二个字符和第三个是不同的，交换后得到bba，和之前的重复了。因此，这种方法不行。

因为abb能得到bab和bba，而bab又能得到bba，那我们能不能第一个bba不求呢？ 我们有了这种思路，第一个字符a与第二个字符b交换得到bab，然后考虑第一个字符a与第三个字符b交换，此时由于第三个字符等于第二个字符，所以它们不再交换。再考虑bab，它的第二个与第三个字符交换可以得到bba。此时全排列生成完毕，即abb、bab、bba三个。

这样我们也得到了在全排列中去掉重复的规则：去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时，要求 [i,j) 中没有与第j个数相等的数。下面给出完整代码：

#include 
  
    #include 
   
     //交换两个字符 void Swap(char *a ,char *b) { char temp = *a; *a = *b; *b = temp; } //在 str 数组中，[start,end) 中是否有与 str[end] 元素相同的 bool IsSwap(char* str,int start,int end) { for(;start 
     
    
  

参考：https://blog.csdn.net/wzy_2017/article/details/

如何按照大小顺序输出一个数字序列的全排列：http://blog.chinaunix.net/uid--id-