秒杀排列组合（上）————排列篇

首先为什么要写排列组合？因为排列组合在数学中占有重要的地位，其与概率论也有密切关系；并且排列组合问题在求职的笔试，面试出现的概率特别高，而我在网上又没有搜到比较全面题型的文章；同时，我觉得编写排列组合程序对学习递归也是很有帮助的；当然，最重要的原因是排列组合本身就很有趣！所以就总结下排列组合的各种问法，分两篇写：上篇写排列，下篇写组合。

排列篇

组合篇地址：http://blog.csdn.net/nash_/article/details/8315418

首先从各大IT公司的题中总结出排列组合的对象都是整形数组或字符数组，排列问题可以按输入数据分为两大类：输入数据有重复和无重复，又可以按输出数据分为两大类：输出数据有重复和无重复；而排列问题也偶尔会考非递归。

首先提一下全排列的几种算法：

由本文的目的是总结排列的各种题型，而不是针对某个题型的各种算法，并且由于篇幅有限，感兴趣的朋友可以参考：

http://cache.baidu.com/cm=9f65cb4a8c8507ed4fece763104c8c711923d030678197027fa3c215cc790b1a0161e4bf233f405a8e90613c47f81641e1a43379360622e4cb998e4c8beb932e7f8a2633734ad74705d36ef58d197bd565cd1abfa00e96b0e741e3b9d3a3c82554dd22026df1f39c2c0203cb1fe76541f4d1985f655a07c9e7&p=8b2a9f0e96934eab5bacd3204a4c&user=baidu

由于侧重点在输入数据无重复，所以先看输入数据无重复类型：

其中又可以分为全排列和分组后排列：

首先写基本的全排列：

如a={1,2,3}。输出123，132，213，231，312，321

这个是最基本，也是最经典的排列

算法思想：可以输出1加上23的全排列，2加13的全排列，3加上12的全排列，运用递归求比如23的全排列..依次递归下去；比如现在要2开头求全排，首先要交换1，2的位置，让a[0]变为2，在用递归求13的所有全排列，前面加个2就是2开头的所有全排列了，最后运用回溯再把1，2调换回来。

代码清单：

import java.util.Arrays;public class PaiLie {       public void runNoRecursionOfPermutation(int[] a){Arrays.sort(a);//对数组排序while(true){printArray(a);//输出一个排列int i;//从后向前，记录一对顺序值中的小值下标int j;//从后向前，记录比i大的第一个数for(i = a.length-2; i >= 0; i--){if(a[i] < a[i+1])//如果找到i跳出break;else if(i == 0)//说明是最大逆序数退出函数return;}for(j = a.length-1; j > i; j--){if(a[j] > a[i])//找到j跳出break;}swap(a, i, j);//交换i，jreverse(a, i+1, a.length-1);//翻转}}public void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}public void reverse(int[] a, int i, int j){while(i < j)swap(a, i++, j--);}public void printArray(int[] a) {for(int i = 0; i < a.length; i++){System.out.print(a[i] + " ");}System.out.println();}public static void main(String[] args) {PaiLie robot = new PaiLie();int[] a = {1,2,3};robot.runNoRecursionOfPermutation(a);}}

如果您有其他的排列问题请告诉博主，谢谢！

==================================================================================================

作者：nash_ 欢迎转载，与人分享是进步的源泉！

转载请保留原文地址：http://blog.csdn.net/nash_/article/details/8351611

===================================================================================================

1楼Little_Stars2小时前

好东西，Thanks~