和风细雨

世上本无难事，心以为难，斯乃真难。苟不存一难之见于心，则运用之术自出。

2008年3月25日 #

全排列算法示例

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<T>{
    public static void main(String[] args){
        String[] arr={"1","2","3"};
        
        Permutation<String> a=new Permutation<String>();
        a.permutation(arr,0,arr.length);
    }
    
    public void permutation(T[] arr,int start,int end){
        if(start<end+1){
            permutation(arr,start+1,end);
            
            for(int i=start+1;i<end;i++){
                T 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 @ 2008-03-25 05:33 和风细雨 阅读(46) | 评论 (0) | 编辑 收藏