有一个比较有趣的问题如下:
假如有五个数字,12345,请列出所有的排列,结果不能重复.
分析:
对于此类排列问题,优先想到递归的方式去处理,那么把问题转换成算法呢?
首先,假如只有三个数字123
那么排列如下
1 -> 23
-> 32
2 -> 13
-> 31
3 -> 12
-> 21
很明显,在最后两个数字时,只需要将它们颠倒一下即可,然后递归结束。刚开始进入递归算法时,列出所有的第一个数字,然后在循环里去调用递归。
实现:
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class ArrangeNumber {
// Added this set for avoiding repetition result;
private static Set<String> set = new HashSet<String>();
/**
* @param args
*/
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(2);
list.add(4);
arrangeNumbers("", list);
}
public static void arrangeNumbers(String header, List<Integer> list) {
// If there are only two elements, display them positive order and negative order, the Recursion method ended
if(list.size() == 2) {
if(!set.contains(header + list.get(0) + list.get(1))) {
System.out.println(header + list.get(0) + list.get(1));
set.add(header + list.get(0) + list.get(1));
}
if(!set.contains(header + list.get(1) + list.get(0))) {
System.out.println(header + list.get(1) + list.get(0));
set.add(header + list.get(1) + list.get(0));
}
return;
}
// Main Recursion logic
for(int i = 0; i < list.size(); i ++) {
List<Integer> templist = new ArrayList<Integer>();
String tempheader = header + list.get(i);
for(int j = 0; j < list.size(); j ++) {
if(i != j) {
templist.add(list.get(j));
}
}
arrangeNumbers(tempheader, templist);
}
}
}
时间复杂度:
首先递归中有双重循环,那么复杂度是N^2.
在递归中,假如3个数字是3次,4个数字是4*3次,可见递归的复杂度是N!
根据算法时间复杂度原则,只保留最高阶,所以该算法的时间复杂度是O(N!)
算法分析中常见的复杂度
O(1) < O(lgn) < O(n) < O(nlgn) < O(n2)< O(n3)<O(2n) < O(n!) < O(nn)
分享到:
相关推荐
本例程通过递归法实现了在易语言中获取排列组合的方法,这在处理大量数据或需要进行各种可能性计算的问题时非常有用。 递归法是解决此类问题的经典策略,它通过将问题分解成更小的子问题来解决。在排列组合问题中,...
在给定的“递归算法实现随机串和全排列的生成”主题中,我们将深入探讨递归在生成随机字符串和全排列问题中的应用。这里我们将主要关注递归的核心概念、如何生成随机字符串以及如何实现全排列,所有这些都是使用C#...
总结来说,从n个数组中取出所有排列组合的Java实现涉及到递归算法、回溯法以及数据结构的操作。理解这些概念并能够熟练运用是成为一名优秀程序员的关键。通过这个例子,我们可以看到如何利用Java的灵活性和表达力来...
同时,我们需要维护一个标记数组,记录哪些元素已经在当前排列中出现过,以确保不会重复使用。 在实际编程中,Python、Java、C++等语言都有成熟的库支持这种问题的解决,例如Python的`itertools.permutations()`...
全排列是指从n个不同元素中取出m个元素(m≤n),按照一定的顺序排成的所有可能的排列方式。例如,对于数字集合{1, 2, 3},其全排列包括{1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, 和 {3, 2, 1}。 在...
本资源深入讲解了如何在Java中实现这两种基本算法。 首先,让我们来理解排列(Permutation)的概念。排列是指从n个不同元素中取出m(m≤n)个元素,按照一定的顺序排成一列的所有可能的方法。在Java中,递归是一种...
该算法的基本思路是:从集合中选择一个元素,放入当前排列中,然后递归地选择下一个元素,直到所有元素都被选择完毕。 下面是递归排列算法的详细流程图: 1. 首先,定义一个 perm 函数,用于输出排列的所有序列。 ...
标题中的“8594 有重复元素的排列问题”是指一种编程挑战,目标是设计一个算法来生成具有重复元素的集合的所有不同排列。描述进一步解释了这个问题,指出需要处理的集合R包含n个可能相同的元素,并且要求列出所有...
在数学上,排列是指从n个不同元素中取出m(m≤n)个元素的所有可能的顺序。如果m=n,即取出所有元素进行排列,那么这个操作称为全排列。对于给定的数据集合,其总排列个数可以通过阶乘来表示,即n!(n的阶乘),即n ...
在全排列问题中,每一步代表一个元素的位置,当所有元素都找到合适位置时,就得到一个排列;若发现当前的排列不可能是有效的全排列,就回溯到上一步,调整元素的顺序。 现在,我们来看如何用Java编写一个递归函数来...
本解决方案使用Java语言实现,通过递归和交换数组元素的方式生成所有排列。 构造方法 在Permutation类中,构造方法`Permutation(int[] a)`用于初始化数组a,并将其赋值给类变量a。 判断是否重复 `isOk(int b, ...
- 在递归过程中,对于每个位置,尝试与之后的所有元素交换位置,并检查是否会产生重复排列。 - 如果发现会产生重复排列,则跳过此次交换。 - 对于每一种有效的排列,将其打印出来,并累加到全局变量 `sum` 中,...
Java中实现排列可以使用回溯法或者迭代法。回溯法是一种试探性的解决问题的方法,当发现某条路径无法达到目标时,就回溯到上一步,尝试其他可能的路径。而迭代法则通常基于索引交换实现,通过遍历所有可能的起始元素...
在实际编程实现中,我们可以创建一个辅助函数,接收当前处理到的元素位置、已选择的元素集合和原始集合作为参数。递归函数在处理完所有元素后,将当前选择的元素集合添加到结果集中。在每次递归调用时,可以选择是否...
### 重复元素排列问题 #### 问题描述 本问题是关于如何设计一个算法来求解具有重复元素的集合的所有不同排列组合。具体来说,给定一个包含`n`个元素的集合`R={r1,r2,… ,rn}`,其中元素之间可能存在重复。目标是找...