`
luxury_zh
  • 浏览: 72715 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

全排列算法——递归版

阅读更多
      今天在阅读《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
       写完后上网一搜全排列,又发现了一些关于这个问题的进一步说明,有多种算法可实现,包括迭代的算法,有兴趣的童鞋可以上网搜一下,了解了解。
分享到:
评论

相关推荐

    全排列——递归排序和字典序列

    ### 全排列——递归排序和字典序列 在计算机科学与编程领域中,全排列是一种重要的算法,它被广泛应用于解决多种问题,如组合优化、密码学等。本文将详细介绍两种实现全排列的方法:递归排列和字典序排列,并通过...

    N个数全排列的非递归算法

    标题 "N个数全排列的非递归算法" 涉及的是计算机科学中的经典问题——全排列。全排列是指从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排成一列的所有可能组合。在这个场景中,非递归算法指的是不依赖递归...

    全排列递归算法的并行化.pdf

    例如,在计算彩票中奖概率、解决NP难问题(如电路板排列)等方面,全排列算法扮演着关键角色。递归算法因其清晰的结构和较强的可读性成为解决全排列问题的常见方法,但其效率相对较低,特别是在处理大规模问题时,...

    递归练习 数据结构实验全排列

    本实验主题为“递归练习 数据结构实验全排列”,主要针对山东大学数据结构课程中的一个经典问题——全排列进行深入探讨。全排列是指从n个不同元素中取出m个元素,按照一定的顺序排列起来,所有可能的排列组合。在...

    西南交通大学数据结构实验报告黑白棋.doxc递归算法设计及堆栈消除递归

    首先,我们来看第一个知识点——递归算法设计。实验要求实现一个黑白棋子交换的游戏,游戏的目标是通过有限步数将初始的棋盘布局(三个白子在前,三个黑子在后)转换为目标布局(三个黑子在前,三个白子在后)。游戏...

    计算机数据结构-全排列回溯算法-java

    在本主题中,我们将重点关注全排列问题及其解决方案——回溯算法,这是一种在计算机科学中用于搜索所有可能解决方案的有效方法,特别适用于解决约束满足问题。 全排列是指从给定集合的所有元素中,不重复地选取所有...

    算法_reachy6w_算法全排列_rhythm2y6_warmis_

    总的来说,掌握全排列算法对于理解递归、回溯以及复杂问题的解决策略至关重要。C语言作为一种基础的编程语言,提供了直接且高效的实现方式。通过实践这些算法,开发者可以提升逻辑思维和编程能力,为解决更复杂的IT...

    字典序、邻位对换、递归递增进位制数法、递归的递减进位制数法生成全排列

    字典序、邻位对换、递归递增进位制数法、递归的递减进位制数法生成全排列。除递归地增是O(n·n!)外,其余三个都是O(n!)。main函数是计算1——12生成全排列的运行时间。

    快速排序算法matlab

    3. **递归排序子序列**:递归地调用快速排序算法,对基准左边的子序列和右边的子序列进行排序。 #### 四、案例分析——生物医学信号处理作业中的快速排序 本案例中,学生齐毅松(学号U200912446)使用快速排序算法...

    内部资料——算法复习整理.doc

    递归在算法设计中非常常见,如阶乘、斐波那契数列、 Ackermann 函数、全排列和整数划分等。然而,递归算法可能导致效率低下,因为它们可能需要重复计算相同的子问题,消耗更多时间和空间。为提高效率,可以将递归...

    数据结构中回溯与递归实验报告

    【描述】:本实验报告主要探讨了在数据结构和算法中回溯法和递归的应用,通过两个具体问题——棋盘覆盖问题和批处理作业调度问题,展示了这两种方法在解决实际问题中的策略和步骤。 【标签】:“word” 【实验分析...

    算法分析——CPP

    数字0~100全排列利用Perm函数对所产生的LIST进行递归排列

    实验1-递归算法1

    在本实验中,我们将探讨递归的实现方式,并通过两个具体的例子——Fibonacci数列和全排列问题——来加深理解。 ### Fibonacci数列 Fibonacci数列是一个典型的递归问题,它的定义是:F(0) = 0, F(1) = 1, F(n) = F...

    数据结构排序算法3

    例如,冒泡排序适合教学和理解排序的基本概念,而全排列算法则在需要找出所有可能排列的场景中大显身手。当然,对于大数据量的排序,更高效的算法如快速排序、归并排序或堆排序通常是首选。 在学习这些算法的同时,...

    java 中的经典递归

    #### 三、Java中经典递归示例——全排列问题 本节将通过一个具体的Java代码示例来详细介绍递归的应用,该示例实现了字符数组的全排列问题。 ```java public class AllSort { public static void main(String[] ...

    算法分析与设计课件

    分治策略则是一种将大问题分解为小问题求解的方法,如经典的排序算法——快速排序和归并排序就是其应用实例。 “算法分析”部分讲解了时间复杂度和空间复杂度的概念,帮助学习者理解算法效率的度量标准。此外,它还...

    算法作业内容要求

    通过本次算法作业的实践,学生不仅能够加深对算法设计与分析基础的理解,还能够掌握两种实用且重要的算法——生成排列的算法和Boyer-Moore算法。这些技能对于后续的计算机科学学习和实际工作都将大有裨益。同时,...

    MATLAB设计_permn彼尔姆算法.zip

    在这个名为"MATLAB设计_permn彼尔姆算法.zip"的压缩包中,包含了一个名为`permn.m`的MATLAB函数文件,这通常意味着它实现了一个特定的算法——彼尔姆算法(Permutation Algorithm)。彼尔姆算法,又称全排列算法,...

Global site tag (gtag.js) - Google Analytics