`
MouseLearnJava
  • 浏览: 465613 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论
阅读更多

本文将给出一个使用回溯法实现全排列的程序。


public class Permutations {

	public void permute(String value, int startIndex, int endIndex) {

		if (startIndex == endIndex) {
			System.out.printf("%s\n", value);
		} else {
			for (int currIndex = startIndex; currIndex <= endIndex; currIndex++) {

				value = swap(value, startIndex, currIndex);

				permute(value, startIndex + 1, endIndex);

				/** 回溯 */
				value = swap(value, startIndex, currIndex);
			}
		}
	}

	private String swap(String value, int idxOne, int idxTwo) {
		char[] charArray = value.toCharArray();
		char temp = value.charAt(idxOne);
		charArray[idxOne] = charArray[idxTwo];
		charArray[idxTwo] = temp;
		return new String(charArray);

	}
}


测试程序如下:

public class Main {
	
	public static void main(String[] args) {
		String value = "ABCD";
		new Permutations().permute(value, 0, value.length()-1);
	}

}


运行结果:
ABCD
ABDC
ACBD
ACDB
ADCB
ADBC
BACD
BADC
BCAD
BCDA
BDCA
BDAC
CBAD
CBDA
CABD
CADB
CDAB
CDBA
DBCA
DBAC
DCBA
DCAB
DACB
DABC
0
0
分享到:
评论

相关推荐

    n全排列输出

    输出n的全排列,有两种方法: 1. 采用递归插入的方法,如果知道n-1的全排列,n的全排列为将数值n插入的n-1的全排列之间的空隙和两头共n个位置。 2. 采用递归标记填充的方法,查看标记数组,将未标记的数值依次填充...

    编写程序输出前n个正整数的字典序全排列

    使用递归 :-------------输入给出正整数n,输出1到n的全排列,排列的输出顺序为字典序,每种排列占一行,数字间无空格,

    java递归实现N个数全排列输出

    在这个场景中,我们将探讨如何使用Java语言,通过回溯法来递归实现全排列的输出。 首先,我们需要理解回溯法的基本概念。回溯法是一种试探性的解决问题的方法,它尝试逐步构建解决方案,并在每一步中检查当前的解...

    N个数全排列c语言算法

    输入N,输出1-N全排列c语言算法,非递归算法................

    构造全排列问题

    4. **输出结果:** 最后,根据数组`data`输出最终的全排列。如果在处理过程中发现无法满足题目要求(例如`n`或字符串`s`的长度不符合题目规定),则输出`-1`。 #### 五、代码实现 下面给出一个具体的C++代码实现...

    c++编写的全排列源代码

    - 最终,程序输出全排列的总数。 ### 总结 本C++程序提供了一个简洁而有效的全排列生成方法,尤其适合初学者理解和学习。通过分析代码,我们不仅能够掌握递归算法的应用,还能深入理解数组管理、条件判断和循环...

    输出n个整数的全排列

    全排列是组合数学中的一个...为了深入理解并完成实验,你需要打开这个文件查看具体内容,包括可能的注释、测试用例以及预期的输出。通过实际编写和运行代码,你可以更好地掌握全排列的概念以及C++的递归和回溯技巧。

    输出有重复字符的全排列

    输出有重复字符的全排列,C++源码......

    python回溯法实现数组全排列输出实例分析

    在介绍的Python回溯法实现数组全排列输出实例中,首先定义了全排列的概念。全排列是指从n个不同元素中取出m个元素的所有可能的排列组合,其中m可以等于或小于n。当m等于n时,我们称之为“全排列”。换言之,全排列是...

    输出n个数字的全排列(可重复)

    如:n=3 全排列的数字为 1 2 3 则输出 123 132 213 231 321 312 2、输入n和k(n》=k)求n个数字的(n,k)排列 如n=3,k=2 输入的三个数位1 2 3 则输出 12 13 21 23 31 32 3、输入n个数(有重复),求n个数字的...

    五个数的全排列

    例如,假设我们有5个数`{1, 2, 3, 4, 5}`,初始状态是未排列的,递归函数会尝试各种可能性,如`[1, 2, 3, 4] + [5]`,然后是`[1, 2, 3, 5] + [4]`等,直到所有可能的排列都被生成并输出。 在实际代码中,我们还需要...

    全排列(阶乘)输出程序

    在本例中,我们关注的是如何用编程语言来实现全排列的输出,特别地,使用了C++这一强大的系统级编程语言。 在C++中,实现全排列通常会借助递归的思想。递归是一种函数或过程调用自身的技术,它可以用来解决复杂的...

    全排列数生成

    输出各行遵循“小数优先”原则, 在各全排列中,较小的数尽量靠前输出。如果将每行上的输出看成一个数字,则所有输出构成升序数列。具体格式见输出样例。 【样例输入1】1 【样例输出1】1 【样例说明1】输入整数N=1,...

    201900302030_邵嘉明_实验一:递归练习1

    3. `main()` 函数:这是程序的入口,负责接收用户输入,初始化数组,调用`Perm`函数输出全排列,并在最后输出"end"。 递归的核心在于函数调用自身,每次调用都解决一个更小的问题。在这个实验中,`Perm`函数通过...

    201700130033_武学伟_实验一1

    //输出全排列 return 0; } 六、结论 本实验报告展示了递归算法在数据结构中的应用,具体来说是递归算法在生成全排列和子集问题中的应用。通过实验,我们熟悉了开发工具的使用,掌握了递归的实现思想,并了解了...

    回溯法 - 输出自然数1到n所有不重复的排列,即n的全排列

    根据给定文件的信息,本文将深入探讨如何使用回溯法来输出自然数1到n的所有不重复排列(即n的全排列)。同时,还将提供一个Java实现的具体示例。 ### 回溯法简介 回溯法是一种通过尝试解决离散和组合问题的方法,...

    序数法全排列

    在main()函数中,我们使用了循环来生成所有可能的全排列,然后将每个全排列输出到屏幕上。 5. 优化策略 在序数法全排列的实现中,我们可以使用一些优化策略来提高算法的效率。例如,我们可以使用动态规划来存储...

    输出n个字符的全排列(没有重复字符)

    简单的实现,代码很短。...输入一个字符串,输出它的字符的所有组合的情况 如输入“abc”,则输出abc,acb,bac,bca,cab,cba。 但如果输入“aba”,即有重复的,也会输出aba,aab,baa,baa,aba,aab。

    Java实现字符数组全排列的方法

    它创建了一个包含 'a', 'b', 'c' 的字符数组,并调用 `permutation` 进行全排列,最后输出所有可能的排列组合。 运行 `testPermutation`,你会看到如下输出: ``` abc acb bac bca cab cba ``` 这正是 'a', 'b', 'c...

Global site tag (gtag.js) - Google Analytics