全排列递归思路讲解

举报
SHQ5785 发表于 2023/08/10 09:12:54 2023/08/10
【摘要】 前言      全排列,full permutation, 可以利用二叉树的遍历实现。二叉树的递归遍历,前中后都简洁的难以置信,但是都有一个共同特点,那就是一个函数里包含两次自身调用。所以,如果一个递归函数中包含了两次自身调用,那么这类问题就是归纳成二分问题。也就是to be or not to be , is the problem。如果一个使用相同手段并且每一个点上可分为两种情况的问题,...

前言

      全排列,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,这样,就列出第一种。如图所示:

      我们可以看到,这里的孩子个数是递减的,直到最后一个元素,就不用选择了,同时也得到一种可能。

      要枚举出所有的,那么就遍历这样一颗树。好了,先上代码。

package cn.edu.ujn.nk;
 
public class FullPermutation {
/**
     * 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[]) {  
        FullPermutation p = new FullPermutation();
        StringBuffer buffer = new StringBuffer();
        String input = "ABCD";
        for (int i = 0; i < input.length(); i++) {  
            p.permutation(input, i, buffer);  
        }  
    }  
}

美文美图

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。