A-A+

排列与组合中的递归策略

2008年11月25日 资源分享 暂无评论 阅读 1 次

排列与组合中的递归策略
16:29 , kono
section 1. 字符串的全排列。譬如假定给定字符串为“abc”,则全排列是“abc”的所有可能组合,且每一个字符都不相关。如“aaa”的全排列仍然有6种(3!=6)。
可以按照字母顺序来排列这些字符。如果输入"abcd",这意味着第一个字符将是“a”打头,其次是“b”...这样的排列就具有如下变化规律:最右边字符的变化将快于左边字符的变化。换句话说,为当前位置选择一个字符,向右移动一个位置进行全排列——递归出现了。 找出位置n的字符的全排列,需要把允许出现在位置n上的字符依次放到位置上,然后为位置n的每一个新字符找出位置n+1的全排列。当n大于字符串的个数时就找到了全排列。此时需要先把当前字符输出,然后回到n-1位置去更改字母(基底情况)。
把程序分为基底情况和递归情况是良好的程序设计方法。一种大幅提高递归效率的优化方法是:如果下次递归进入基地情况,则不再递归而是直接进入基底。以全排列为例,将减少n!次函数调用。这种直接进入基底的优化方法称为“断臂递归(arms length recurision)”.下面是全排列的AS3代码:

class Permute
{
public static function permute(test:String):void
{
var out:Array = new Array(test.length);
var used:Array = new Array(test.length);
for(var i:uint = 0; i < used.length; i++) used[i] = false; doPermute(test,out,used,0); } private static function doPermute(inString:String, out:Array, used:Array, recursLen:uint):void { var i:uint; if(used.length == recursLen) { trace(out); return; } for(i = 0; i < used.length; i++) { if(used[i]) continue; out[recursLen] = inString.charAt(i); used[i] = true; doPermute(inString,out,used,recursLen + 1); used[i] = false; } } } section 2. 字符串的全组合。组合与排列不同的一点是,如果输入“abc”,则“ab”与“ba”是一种组合,而“ab”与“bc”才是不同的组合。组合的算法使用递归实现仍然极其方便: 对从输入起点字符到输入字符串的最后一个字符之间的各个字符,循环: 为输出字符串(数组)的当前字符选择一个字符 把这些字符输出到输出字符串(数组)里 如果当前字符不是输入字符串的最后一个字符 从下一个位置开始生成全排列,循环将从当前字符后面的字符开始 代码如下: class Combine { public static function combine(test:String):void { var out:Array = new Array(test.length); doCombine(test,out,0,0); } private static function doCombine(inString:String, out:Array, recusLen:uint, start:uint):void { for(var i:uint = start; i < out.length; i++) { out[recusLen] = inString.charAt(i); if(recusLen < out.length-1) out[recusLen + 1] = ""; trace(out); if(i < out.length - 1) doCombine(inString,out,recusLen + 1,i + 1); } } } section 3. 压轴大戏:电话键单词组合。手机的拨号盘上每一个数字对应三个字母。如何对给点的一个电话号码输出全部单词的排列? 写出几种排列后将发现,这些排列中某位置的字母将影响右边的字母。即当位置i处的字母发生变化时,i+1处的单词将轮遍取到所有可能的值。i与I+1构成了递归关系。so: 如果当前数字超出了最后一位数字 输出当前单词 否则 对当前位置所对应的三个字母,按照从低到高的顺序喜欢 用字母代替当期数字 前进到下一个数字并且递归 如果当前数字是0或者1则返回(0,1没有对应字母) 算法代码: class PrintPhoneNumber { private static const PHONE_NUMBER_LENGTH:uint = 7; public static function iterPrintPhoneNum(phoneNum:uint):void { var result:Array = new Array(PHONE_NUMBER_LENGTH); doPrintPhoneNum(phoneNum, 0, result); } private static function doPrintPhoneNum(phoneNum:uint, curDigit:uint, result:Array):void { var i:uint; if(curDigit == PrintPhoneNumber.PHONE_NUMBER_LENGTH) { trace(result); return; } for(i = 1; i <= 3; i++) { var p:uint = uint(phoneNum.toString().charAt(curDigit)); result[curDigit] = getCharKey(p,i); doPrintPhoneNum(phoneNum, curDigit + 1, result); p = uint(phoneNum.toString().charAt(curDigit)); if( p== 0 || p == 1) return; } } private static function getCharKey(phoneKey:uint, place:uint):String { var key:Array =[ [null,null,null], [null,null,null], ["a","b","c"], ["d","e","f"], ["g","h","i"], ["j","k","l"], ["m","n","o"], ["p","r","s"], ["t","u","v"], ["w","x","y"] ]; return key[phoneKey][place-1]; } } 该题另外有一种循环解法: 一个字母一个字母的创建出第一个单词 无限循环 输出当前单词 递增最后一个字母并且对它前面的字母做相应改变 如果第一个字母已经改变,解除循环 public static function CricPrintPhoneNum(phoneNum:uint):void { var i:int; var result:Array = new Array(PHONE_NUMBER_LENGTH); for(i = 0; i< result.length; i++) result[i] = getCharKey(uint(phoneNum.toString().charAt(i)),1); while(true) { trace(result); for(i = PHONE_NUMBER_LENGTH - 1; i >= -1; i--)
{
var a:uint;
if(i == -1)
return
if(getCharKey(uint(phoneNum.toString().charAt(i)),3) == result[i] ||
uint(phoneNum.toString().charAt(i)) == 0 ||
uint(phoneNum.toString().charAt(i)) == 1)
{
result[i] = getCharKey(uint(phoneNum.toString().charAt(i)),1);
}
else if(getCharKey(uint(phoneNum.toString().charAt(i)),1) == result[i])
{
result[i] = getCharKey(uint(phoneNum.toString().charAt(i)),2);
break;
}
else if(getCharKey(uint(phoneNum.toString().charAt(i)),2) == result[i])
{
result[i] = getCharKey(uint(phoneNum.toString().charAt(i)),3);
break;
}
}
}

}

给我留言

Copyright © 浩然东方 保留所有权利.   Theme  Ality 07032740

用户登录