排列组合-插入算法
1.问题描述
将字符'1','2','2','3','4'的所有的组合用一个算法排列出来。
2.问题分析
这是一个排列问题,排列个数与参与排列的元素个数有关。假设参与排列的元素个数
为n,那么排列数等于n的阶乘,即F(n)=n!。n! = 1 * 2 * 3 * ... * n.
本文问题描述中出现了重复元素,最后排列中有很多重复的排列需要去掉。本文介绍一种
插入算法来解决这个问题。
所有的插入算法的一个共同点:从最小问题单元开始递推。
结合下面的图示开始递推。
图2-1
(1)当只有一个元素时,排列数为1,即一种排列。排列:
[1]
(2)当有两个元素时,排列数为2。排列:
[2,1],[1,2]
(3)当有三个元素时,排列数为1 * 2 * 3 = 6。排列:
[3,2,1],[2,3,1],[2,1,3],[3,1,2],[1,3,2],[1,2,3]
......
以此类推。
3.算法实现
将一个字符查到一个排列字符数组中:
char [][] insert(char [] a,char b) {
int row = a.length+1;
int col = row ;
int insertPos = 0;//插入位置
char [][] r = new char[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if(j < insertPos) {
r[i][j] = a[j];
} else if(j > insertPos ){
r[i][j] = a[j-1];
} else {
r[i][j] = b;//插入新的字符
}
}
insertPos++;//插入位置向后移动
}
return r;
}
主算法:
char [][] composition(char [] c) {
//存储排列组合后的结果
char [][] r = {{c[0]}};
//存储每次插入一个字符以后的所有结果。
char [][][] d ;
int ii;
for (int i = 1; i < c.length; i++) {
d = new char[r.length][0][0];
//插入新的字符
for (int j = 0; j < r.length; j++) {
d[j]=insert(r[j],c[i]);
}
//将d中的结果存放到r
r = new char[d.length*d[0].length][0];
ii = 0;
for (int j = 0; j < d.length; j++) {
for (int j2 = 0; j2 < d[j].length; j2++) {
r[ii++] = d[j][j2];
}
}
}
return r;
}
过滤算法:
Set<String> removeRepeat(char [][]r) {
Set<String> set = new HashSet<String>();
for (int i = 0; i < r.length; i++) {
set.add(new String(r[i]));
}
return set;
}
4.扩展
当有重复元素时,最后排列数为多少?
在回答上面的问题之前我们先通过本文中的算法测试一下。
测试代码:
public static void main(String[] args) {
Composition com = new Composition();
// new char[]{'1','2','3','4','2','2'}
// new char[]{'1','2','3','4','2','2','2'}
char [][] r = com.composition(new char[]{'1','2','3','4','2'});
System.out.println(r.length);//过滤前
Set<String> set = com.removeRepeat(r);
System.out.println(set.size());//过滤后
// Iterator<String> it = set.iterator();
// while (it.hasNext()) {
// System.out.println(it.next());
// }
}
测试结果:
(1)重复一次时,(这里重复元素为2):
new char[]{'1','2','3','4','2'}
结果:120,60
(2)重复两次时:
new char[]{'1','2','3','4','2','2'}
结果:720,120
(3)重复三次时:
new char[]{'1','2','3','4','2','2','2'}
结果:5040,210
......
通过逐一排列的过程可知,在排列中所有对于一个元素的所有重复元素在排列中的任何位置的机会概率是均等的。假设只有一个元素重复,则一个元素重复m次(总共有m+1个元素)后最终的排列数为F(n)= n!/(m+1)!。
5.总结
通过本文的学习,大家至少知道了一种排列的算法【插入算法】。但这不是最重要的,重要的是学会如何去分析,分解问题。将复杂问题简单化,找到其最小问题单元。从最简单的入手。因为人本身的Memory,CUP和Hard与计算机相比极为有限,并且这种差距还在与日俱增。所以我们只能先处理好最简单的最基本的问题,在接触计算机帮助我们处理复杂问题。
- 大小: 4 KB
- 大小: 19.6 KB
分享到:
相关推荐
leetcode爬楼梯排列组合解法 Data Structure and Algorithmic Practice 【任务1 - 数组与链表】 1、数组 实现一个支持动态扩容的数组 实现一个大小固定的有序数组,支持动态增删改操作 实现两个有序数组合并为一个...
算法 数组 二分查找 - , 找到最大滑动窗口 - 搜索旋转数组 - 找到最小的公数 - 旋转阵列 - 查找低/高指数 - 向左移动零 - 找到最大单笔卖出利润 - 实施快速排序 - 合并重叠区间 - 两个值之和 - , 链表 反转单向链表 ...
排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良的选择排序...
排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - ...
本文实例讲述了JS实现的全排列组合算法。分享给大家供大家参考,具体如下: 全排列组合算法,例如a,b,c,d进行全排列组合,则组合结果为:a,b,ab,c,ac,bc,abc,d,ad,bd,abd,cd,acd,bcd,abcd。实现思路:从数据源拿出一...
排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良...
排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - ...
1.排列的生成:(1..n) 2.组合的生成(1..n中选取k个数的所有方案) 九.查找算法 1.折半查找 2.树形查找 十、贪心 *会议问题 (1) n个活动每个活动有一个开始时间和一个结束时间,任一时刻仅一项活动进行,求...
排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap ...
排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - ...
27.排列组合 60 28.格雷码(Gray Code) 61 29.产生可能的集合 63 30.m元素集合的n个元素子集 66 31.数字拆解 68 32.得分排行 71 33.选择、插入、气泡排序 73 34.Shell 排序法 - 改良的插入排序 77 35.Shaker 排序法...
排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - ...
• 排列组合 • 格雷码(Gray Code) • 产生可能的集合 • m元素集合的n个元素子集 • 数字拆解 排序 • 得分排行 • 选择、插入、气泡排序 • Shell 排序法 - 改良的插入排序 • Shaker 排序法 - 改良的...
排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良...
排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - ...
排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - ...
排列组合 格雷码(Gray Code) 产生可能的集合 m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良...