今天在阅读《Java数据结构与算法 第二版》的时候,看到了一个关于全排列的问题。给出的例子是如何排列出 字母c,a,t所有的不同组合。我按照递归的思路写了一下,成功运行。大致思路是,固定第一个元素,把剩余的全排列,然后数组向左轮转(最左边的转到最右边)然后重复这个过程直到数组中的每一个元素都出现在了第一的位置。
下面是代码:
package com.luxury.algorithm.recursion;
/**
* @author luxury_zh
* work out all the arrangements of the given numbers.It is a recursion
* algorithm which works like this:fix the first left number of the
* remaining array(at the beginning,it's just the given array) then arrange
* the right numbers.Next,the important thing is a rotation after one
* arrangement. Rotation means moving every element to its previous position
* (the first left element moves to the rightmost)
* Do the same steps until there is only one number in the remaining array.
*/
public class FullArray {
public static int[] array={1,2,3,4};
public static void main(String args[])
{
//execute the algorithm
doArrange(array.length);
}
public static void doArrange(int remainingSize)
{
if(remainingSize==1)
{
//print out the array
display(array);
System.out.print(" ");
return;
}
for(int i=0;i<remainingSize;i++)
{
//recursion:arrange the remaining numbers
doArrange(remainingSize-1);
//do rotation after one arrangement
rotate(remainingSize);
}
}
public static void display(int[] array)
{
for(int e : array)
System.out.print(e);
}
public static void rotate(int remainingSize)
{
int length=array.length;
int firstLeft=array[length-remainingSize];
for(int i=remainingSize;i>1;i--)
{
array[length-i]=array[length-i+1];
}
array[length-1]=firstLeft;
}
}
输出结果:1234 1243 1342 1324 1423 1432 2341 2314 2413 2431 2134 2143 3412 3421 3124 3142 3241 3214 4123 4132 4231 4213 4312 4321
写完后上网一搜全排列,又发现了一些关于这个问题的进一步说明,有多种算法可实现,包括迭代的算法,有兴趣的童鞋可以上网搜一下,了解了解。
分享到:
相关推荐
全排列算法有两个比较常见的实现:递归排列和字典序排列。 (1)递归实现 从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,从而得到所有元素的全排列。 (2)字典...
算法思想——递归与分治 算法思想——递归与分治
自己写的基于字符的全排列算法,代码简洁,高效,7位数的全排列都是秒排!用到了广度优先排列,深度优先搜索和几个递归,唯一没完成的是退出时释放内存,呵呵,破解密码时超有用的哟,,
全排列-非递归算法(适合动态的新元素加入重新输出全排列-本程序以1到6的数字输出为例)
一种新型径向基函数神经网络学习算法 ———递归正交最小二乘法(ROLS)
算法设计,PPT,算法分析与设计,老师多年积累,很详细全面的算法讲解——递归,分治
全排列算法
全排列算法详细解析(完整版)
基于全排列算法的完整代码解析,可供理解搜索的技巧,有很高的使用价值
c语言分治法求众数重数-五大常见算法策略之——递归与分治策略,算法数据结构 五大常用算法
全排列算法: 比如字符串abc,全排列结果为abc,acb,bac,bca,cba,cab。
使用递归实现的全排列算法,输出所有的全排列。 各种主流程序设计语言实现!
该料详细介绍了算法中的一种典型思想———递归与分治
计算机算法——设计与分析导论(第三版).pdf 英文版
数据结构与算法——C++版(第3版)源文件
全排列算法
数据结构与算法——C++版(第2版)
C语言中递归是重中之重的部分,多数用于求解N!等含有迭代性质的问题,此文档详细介绍了递归算法,实用。
全排列算法 实例 一种实现了n个数全排列的算法 全排列算法 实例 一种实现了n个数全排列的算法
数据结构与算法——C++版