public class toAllRanges { private static int div=0; private boolean printHead=true; private static void swap(int []array,int a,int b ){//定义a b位置交换 int temp=array[a]; array[a]=array[b]; array[b]=temp; } public void outputString(int[]nums){//打印数组 for(int i=0;i<nums.length;i++){ System.out.print(nums[i]); } System.out.print(" "); if(++div%20==0){ //每行20个 System.out.println(); } } /** * @param nums * /*邻位对换法 *邻位对换法中下一个排列总是上一个排列某相邻两位对换得到的。以4个元素的排列为例， *将最后的元素4逐次与前面的元素交换，可以生成4个新排列： *1 2 3 4 1 2 4 3 1 4 2 3 4 1 2 3 *然后将最后一个排列的末尾的两个元素交换，再逐次将排头的4与其后的元素交换，又生成四个新排列： *4 1 3 2 1 4 3 2 1 3 4 2 1 3 2 4 *再将最后一个排列的末尾的两个元素交换，将4从后往前移： *3 1 2 4 3 1 4 2 3 4 1 2 4 3 1 2 *如此循环既可求出全部排列。*/ public void swapOnBorder(int []nums){ System.out.println("*****************************采用邻位对换法算法************************"); int count=1; for(int i=3;i<nums.length;i++){//找出n!/2个循环 count*=i; } for(int i=0;i<count;i++){ outputString(nums); int j=nums.length-2; while(j>=0){ swap(nums,j,j+1); outputString(nums); j--; } swap(nums,nums.length-2,nums.length-1); outputString(nums); int k=0; while(k<nums.length-1){ swap(nums,k,k+1); outputString(nums); k++; } swap(nums,0,1); } } /** * @param nums 传入的整型数组 * 字典序算法如下： * 设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn * 1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j * * =max{i|pi<pi+1} * 2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}（右边的数从右至 * * 左是递增的，因此k是所有大于pj的数字中序号最大者） * 3）对换pi，pk * 4）再将pj+1......pk-1pkpk+1pn倒转得到排列p''=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这 * 举个例子 如 51243 从右到左找到第一个小于其右边的数，即为2 * 然后再从右到左找个第一个比2大的数，即比2大的最小数为3 然后倒换2，3 得到 51342 * 然后再将从2前一位开始全部倒序 即得到51324 即为下一个数字 如此循环即得到所有的组合 */ public void dictionaryMethod(int[]nums){ System.out.println("******************************采用字典序算法****************************"); outputString(nums); int i=nums.length-2; int j,k; int count=1; while(i>=0){ if(nums[i]<nums[i+1]){//从右到左找到第一个小于其右边相邻数的nums[i] j=nums.length-1; while(i<j){ //找到从右到左第一个比nums[i]大的数字 if(nums[i]<nums[j]){ break; } j--; } swap(nums,i,j);//交换nums[i]和nums[j] k=nums.length-1; while(i+1<k){//此处实现nums[i+1]到最后数字的倒转 swap(nums,i+1,k); i++; k--; } outputString(nums); i=nums.length-2;//i要重新定位到倒数第二个数 } else { i--; } } } /** * @param nums 传入的数组 * @param size 在循环交换nums数组中的存在的排列数个数 * 循环移位法 * 如果已经生成了z-1个元素的排列，则在每个排列后添加元素k使之成为k个元素的排列，然后将每个 * 排列循环左移（右移），每移动一次就产生一个新的排列。 * 例如2个元素的排列是1 2和2 1。在1 2 后加上3成为新排列1 2 3，将它循环左移可再生成新排列1 3 2、3 1 2， * 同样2 1 可生成新排列2 1 3、1 3 2和3 2 1。 */ public void rotateSwap(int[]nums,int size){ if(size>nums.length){ //如果数组中的数全部进入了， 就 打印出来 if(printHead){ System.out.println("********************************循环交换法************************************"); printHead=false; } outputString(nums); } else{ for(int i=0;i<size;i++){ //数组中进入size个数 就能产生size种排序，比如进入了123三个数字 通过循环左移 可以产生312，123，231三种 int buffer=nums[0]; for(int j=1;j<size;j++){ //此处完成循环左移 或者循环右移，以左移为例，先把第一个数保存，然后从第一数开始 依次赋值前面数的值………… nums[j-1]=nums[j]; } nums[size-1]=buffer; rotateSwap(nums,size+1); } } } /** * @param nums * @param k */ public void recursiveMethod(int[]nums,int k) { if (k==nums.length) { if(printHead){ System.out.println("********************************递归算法************************************"); printHead=false; } outputString(nums); } else { for (int i = k; i <nums.length; i++) { swap(nums,k,i); recursiveMethod(nums,k+1); swap(nums,k,i); } } } /** * @param nums * @param k * 回溯法通常是构造一颗生成树.回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。 * 回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 */ public void retrospect_Method(int []nums,int k){ boolean available; if(k==nums.length-1){ if(printHead){ System.out.println("*********************************回溯法********************************"); printHead=false; } outputString(nums); } else{ for(int i=1;i<=nums.length;i++){ available=true; nums[k]=i; //给nums数组第k个元素赋值 for(int j=0;j<k;j++){ if(i==nums[j]){ //检查第k个元素前是否存在重复元素 available=false;//有重复的置为false，重新赋值 break; } } if(available==true){ retrospect_Method(nums,k+1); } } } } public static void main(String args[]){ int[]array={1,2,3,4,5}; int[]array_1={1,2,3,4}; toAllRanges range=new toAllRanges(); range.dictionaryMethod(array); range.swapOnBorder(array_1); range.div=0; System.out.println(); range.rotateSwap(array, 1); range.printHead=true; range.recursiveMethod(array,0); range.printHead=true; range.retrospect_Method(array,0); }}
