全排列,full permutation, 经常用于博彩行业。当然我也是一时心血来潮,突然想看看具体如何实现。
这里,我选择递归,因为递归的用法真是多种多样,而且这里正好也反应了一个事实,递归对应着数据结构中的树。
根据二叉树的递归遍历,我们认识到了递归的强大,而她的故事也远远不止于此。这里要说的是,二叉树的递归遍历,前中后都简洁的难以置信,但是都有一个共同特点,那就是一个函数里包含两次自身调用。
所以,如果一个递归函数中包含了两次自身调用,那么这类问题就是归纳成二分问题。也就是to be or not to be , is the problem。如果一个使用相同手段并且并且每一个点上可分为两种情况的问题,基本都可以转化为递归问题。当然,如果是有三个孩子的树,那么我们可能需要在一个递归函数中调用自身三次。
这里的递归,和我们计算阶乘的又有不一样,因为她没有返回,是发散的。也就是从一个节点,发散到N个节点,我们要的结果是叶子节点。
计算全排列,我们可以单独拿出每一个元素作为根节点来构成一棵树,所有的可能排列情况就都隐藏在森林中了。现在来看每一颗树,假如4个元素 , A, B, C, D,以A为根是第一颗,表示以A开头的排列。
那么,第二个位置可以选着 B,C, D,如果我们选择了B,那么B下还有 C, D可以选择, 如果我们选了C,那么最后只剩下D,这样,就列出第一种。如图所示:
我们可以看到,这里的孩子个数是递减的,直到最后一个元素,就不用选择了,同时也得到一种可能。
要枚举出所有的,那么就遍历这样一颗树。好了,先上代码。
/** * recursive method, used for the tree traversal. * * @param inStr * the elements need to be choose * @param pos * the position of the elements we choose * @param parentData * the elements have been chosen */ public void permutation(String inStr, int pos, StringBuffer parentData) { if (inStr.length() == 0) { return; } if (inStr.length() == 1) { System.out.println("{" + inStr + "}"); return; } // here we need a new buffer to avoid to pollute the other nodes. StringBuffer buffer = new StringBuffer(); // copy from the parent node buffer.append(parentData.toString()); // choose the element buffer.append(inStr.charAt(pos)); // get the remnant elements. String subStr = kickChar(inStr, pos); // got one of the result if (subStr.length() == 1) { buffer.append(subStr); System.out.println(buffer.toString()); return; } // here we use loop to choose other children. for (int i = 0; i < subStr.length(); i++) { permutation(subStr, i, buffer); } } // a simple method to delete the element we choose private String kickChar(String src, int pos) { StringBuffer srcBuf = new StringBuffer(); srcBuf.append(src); srcBuf.deleteCharAt(pos); return srcBuf.toString(); }
真的很简洁。测试一下。
public static void main(String args[]) { Permutation p = new Permutation(); StringBuffer buffer = new StringBuffer(); String input = "ABCD"; for (int i = 0; i < input.length(); i++) { p.permutation(input, i, buffer); } }
注意,这个方法实际上还不能单独使用,必须使用循环把每一个元素都考虑进去。
或许你还有更简洁的方法。当然,从性能上看,递归不是很好。但是我觉得可以考虑从树上去分析。
好了,有空贴上c版本的。
C版本:
http://airu.iteye.com/admin/blogs/1936366
相关推荐
全排列递归算法,在VC下调试OK,递归算法简单快捷,大家理解理解
JAVA递归实现全排列算法,含实现源代码,如a、b、c、d的全排列为: abcd abdc acbd acdb adcb adbc bacd badc bcad bcda bdca bdac cbad cbda cabd cadb cdab cdba dbca dbac dcba dcab dacb dabc
全排列算法有两个比较常见的实现:递归排列和字典序排列。 (1)递归实现 从集合中依次选出每一个元素,作为排列的第一个元素,然后对剩余的元素进行全排列,如此递归处理,从而得到所有元素的全排列。 (2)字典...
全排列的非递归实现。 输入1,2,3,4 得到 [1 2 3 4]..........[4 3 2 1]所有24种排列
山东大学 数据结构实验 全排列 递归练习
排列:从n个元素中任取m个...算法思路: (1)n个元素的全排列=(n-1个元素的全排列)+(另一个元素作为前缀); (2)出口:如果只有一个元素的全排列,则说明已经排完,则输出数组; (3)不断将每个元素放作第一个元素,然
用回溯法递归实现的输出N的全排列 如 123 132 。。。。
全排列-非递归算法(适合动态的新元素加入重新输出全排列-本程序以1到6的数字输出为例)
java 递归,abcd全排列,非常简单的。
用C语言写的一个递归全排列算法,附有较为详细的注释。
php全排列递归算法代码,需要的朋友可以参考下
去重全排列的递归实现 去掉重复数字的 全排列的 递归实现
Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE程序 递归Java SE...
常见得全排列有三种解决方案,for循环穷举,stl摸板函数next_permutation,还有DFS深度优先搜索,当我们遇到带有重复的字符串时应该考虑除去重复的部分。
自己整理的关于全排列的递归程序.本例以数组{a,b,c}三个元素作为例子详细讲解。里面的程序都经过VC6.0运行通过,请读者放心使用
递归实现元素全排列
对于求解全排列问题有最暴力的递归枚举法,但是我们希望可以优化时间,因此出现了...其实跟暴力枚举思路差不多,每次递归枚举第x个数字是几,之后a[x]可以选择不动,也可以选择与后面任意一个数交换位置,就是从后面选
递归实现元素全排列
主要介绍了Java基于递归解决全排列问题算法,结合实例形式分析了Java使用递归算法解决全排列问题的原理与具体实现技巧,需要的朋友可以参考下