全排列算法示例

package com.sitinspring;

/**
* 全排列算法示例
如果用P表示n个元素的排列，而Pi表示不包含元素i的排列，(i)Pi表示在排列Pi前加上前缀i的排列，那么，n个元素的排列可递归定义为：
如果n=1，则排列P只有一个元素i
如果n>1，则排列P由排列(i)Pi构成（i=1、2、

.、n-1）。
根据定义，容易看出如果已经生成了k-1个元素的排列，那么，k个元素的排列可以在每个k-1个元素的排列Pi前添加元素i而生成。
例如2个元素的排列是1  2和2   1，对3个元素而言，p1是2  3和3  2，在每个排列前加上1即生成1 2 3和1 3 2两个新排列，
p2和p3则是1  3、3  1和1  2、2  1，
按同样方法可生成新排列2 1 3、2 3 1和3 1 2、3 2 1。
* @author: sitinspring(junglesong@gmail.com)
* @date: 2008-3-25
*/
public class Permutation{
    public static void main(String[] args){
        String[] arr={"1","2","3"};
        Integer[] arr02={4,5,6,7};
        permutation(arr02,0,arr02.length);
    }

    public static void permutation(Object[] arr,int start,int end){
        if(start<end+1){
            permutation(arr,start+1,end);

            for(int i=start+1;i<end;i++){
                Object temp;

                temp=arr[start];
                arr[start]=arr[i];
                arr[i]=temp;

                permutation(arr,start+1,end);

                temp=arr[i];
                arr[i]=arr[start];
                arr[start]=temp;
            }
        }
        else{
            for(int i=0;i<end;i++){
                System.out.print(arr[i]);
            }
            System.out.print("\n");
        }
    }
}

posted on 2008-03-25 05:46 sitinspring 阅读(492) 评论(1) 编辑收藏所属分类: 算法数据结构

# re: 全排列算法示例 2008-04-25 14:47 binz

看了半天还是没怎么懂
请问大侠能不能详细说明一下
像我这样的菜鸟理解起来比较困难

先谢谢了回复更多评论

新用户注册刷新评论列表


只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻知识库 C++博客博问管理
相关文章: 用递归和扫描解决称球问题二叉树搜索树代码蔓延法判断两个城市的连接状态八皇后回溯版轮圈数数退出问题泛型单链表类泛型动态数组类整形数组实用类,用于求两数组的并交差集求最大价值轰炸目标求两字符串的公共子串

# re: 全排列算法示例 2008-04-25 14:47 binz

春风博客

导航

统计

公告

常用链接

留言簿(11)

随笔分类(224)

随笔档案(126)

个人软件下载

我的其它博客

我的邻居们

最新随笔

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

全排列算法示例

评论