排列的递归解法中,给出了排列的递归解法,其实他还存在着非递归解法,以下是一个java program,完成了这个任务。

http://6s4sca.blu.livefilestore.com/y1piEyzPSyDdokE2zqnHMOjIC_yr0-sj8qLnJ1TJtW49JbhkcfKdf0oSLjDg7yZCB-L2EVl5bc3Sryb8CH4OaMnn9J8NJLNKxgj/notrecursivepermutation.java?download

基本思路模式:

  1. 设定栈初始指针,设定现场
    此例中栈指针是top,现场是selected,stack和stry
  2. 当这个栈指针满足某个条件时进入循环一
    此例中是top>=0
  3. 循环一开始对top做尝试,尝试可行则进入下一层,否则所有方法尝试完毕后就需要返回上一层,即退栈
    此例中 if(j==level){  即为退栈条件,在退栈分支中恢复现场
    else 即为进栈条件,在进栈分支中要保存现场selected,stack和stry;另外在此分支中我们可以知道到达栈的第几层,决定是否要开始下一层尝试等

运用这个方法,可以解决为偶然的眼光(续一)中的递归方案写非递归的code。

扩展:

  1. 稍微改动源程序,我们就可以得到排列P(n,m)的解法,即从n个不同球中取m个做有顺序的排列个数。http://6s4sca.blu.livefilestore.com/y1pVzQ1NPWlNSzpXhI7G5gejmUWh8bfBmnhYX2qAOADhdjhLWyn1E3SCWD7EO8r7gI5dvgTNwwmc707yZvkIC8c5EOjir_mmS70/notrecursivepermutation_n_m.java?download
  2. 稍微改动源程序,我们就可以得到组合C(n,m)的解法,即从n个不同球中取m个做无顺序的组合个数。
    http://6s4sca.blu.livefilestore.com/y1ps_m7L6J8ilHYFP4YrE9oeZTSkuAxPyJFwkZoER4Ahj60ld2pEJ8JTer4Ku_XbcRXWw5V9UESmvStitvIDsKH6ywiELj-y3hT/notrecursivecombination_n_m.java?download

参考:

  1. 栈(stack)在预测中的作用
Advertisements