http://www.iteye.com/topic/770382提到:
4.1~20的整数的全排列,因为不才以前也研究过排列组合的问题,于是有了本专题。
最近的专题更多的是在给条鱼人家吃,没有讲怎么捕鱼。所以今天在介绍优雅代码之前,提出一个解决问题的方法论。
复杂问题都是由简单问题组成的,先解决简单问题。
言简意赅,任何复杂问题都是纸老虎。当你面对99*99时,你就要考虑将他变成1+1,然后解决1+1。
有了这个方法论,面对1-20的全排列。你知道怎么做了吧。没错,转变成AB的全排列。
AB: AB BA
太简单了,加个“C”吧。
ABC:
ABC
ACB
BAC
BCA
CAB
CBA
看见标红色的字母了吧,无视它的存在, 就变成了 AB ,BC,AC 的 全排列。
大问题可沿用小问题的解法,让你想到了什么。一个是递归,一个是动态规划。这里显然适合用递归。
假设有n个字符,基本的算法就是:
1.n>2时,变成n-1问题
2.n=2时,输出
3.滚动数组
于是,一个优雅的方案浮出水面:
/**
* 创建时间:2010-9-25 下午12:22:15
* 项目名称:Test
* @author Y.Guo
* @version 1.0
* @since JDK 1.6
* 文件名称:FullArrange.java
* 类说明:全排列
*/
public class FullArrange {
private char[] element;
private int length;
public void arrange(char[] element){
this.element = element;
this.length = element.length;
deal(length);
}
private void deal(int size){
if(size == 1)
return;
for (int i = 0; i < size; i++) {
deal(size - 1);
if(size == 2){
print();
}
rotate(size);
}
}
private void rotate(int size) {
int firstP = length - size;
char first = element[firstP];
int i;
for (i = firstP + 1; i < length; i++) {
element[i - 1] = element[i];
}
element[i -1] = first;
}
private void print() {
for (int i = 0; i < length; i++) {
System.out.print(element[i]);
}
System.out.print("\t");
}
public static void main(String[] args) {
FullArrange tool = new FullArrange();
char[] elem = {'1','2','3','4','5'};
tool.arrange(elem);
}
}
至于组合问题,请听下回分解。
分享到:
相关推荐
采用模块化设计,可以任意调用,如:热点排行(能根据页面自动判断分类排行)、导读、焦点、推荐、搜索等,版面可由你自由组合,更多个性化。 可视化新闻添加方式,可以粘贴网页任意图片、表格、文字,就象WORD一样...
leetcode 递归专题追求-核心-iOS-DSA-实践 Swift 数据结构和算法以及练习。 周 第 1 周:大 O 表示法、递归、排序概述、ADT ...阶乘斐波那契质数最大公约数排列组合几何级数 代码挑战站点 阅读资源
源代码清单(按照库排列) com.javapatterns.abstractfactory 抽象工厂模式 com.javapatterns.adapter 适配器模式 com.javapatterns.bridge 桥梁模式 com.javapatterns.builder 建造者模式 ...
4,修复专题首页的错误。 5,修复播放页面if标签的问题。 6,其他细节的调整。 主要功能: 1,全新的后台操作页面,ajax化操作方式,减少页面数量和刷新,全新的体验感受。 2,分类列表,搜索页面支持多...
随机排列算法 理解C#中的委托[翻译] 利用委托机制处理.NET中的异常 与正则表达式相关的几个小工具 你真的了解.NET中的String吗? .NET中的方法及其调用(一) 如何判断ArrayList,Hashtable,SortedList 这类对象是否...
4,修复专题首页的错误。 5,修复播放页面if标签的问题。 6,其他细节的调整。 主要功能: 1,全新的后台操作页面,ajax化操作方式,减少页面数量和刷新,全新的体验感受。 2,分类列表,搜索页面支持多参数...
1.9.3排列组合、概率论应用、应用统计 34 1.9.4线性规划 37 专题二:程序语言部分 39 1、程序语言知识 39 1.1 程序语言: 39 1.2 汇编语言: 42 1.3 解释程序: 42 1.4 编译程序: 43 2.重点与难点 45 2.1文法及...
同时提供GBK和UTF-8软件包,用户可以根据需要把模板和语言包翻译成其他语言,为多语言环境的开发提供了便利,助你的站点迈向世界。 17 、支持多级管理权限控制,让网站多人维护更轻松 系统支持按频道和模块分别...
本版本是asp+mssql版本,如本机调试运行,需要安装IIS和MSSQL数据库,附加...5、产品列表页默认采用4列大图排列组合,此产品列表展示方式为目前主流服装网站的产品排列模式。 6、更多功能暂不一一列出,可充分体验试用。
5.4.8 在列表控件中滚动、排列、排序和查找 205 5.4.9 在列表控件中实现工作区 205 5.4.10 处理列表控件中的通知消息 206 5.4.11 更改列表控件样式 206 5.4.12 虚拟列表控件 207 5.4.13 列表控件的消息映射 209 ...