用java實現換位法生成全排列 – JAVA編程語言程序開發技術文章

import java.util.ArrayList; 
import java.io.*; 
 
//換位法生成全排列  
class ReplaceArrangement{ 
 
    //從控制臺讀入數據  
    private static String readDataFromConsole(String prompt) { 
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
            String str = null; 
            try { 
                    System.out.print(prompt); 
                    str = br.readLine(); 
 
            } catch (IOException e) { 
                    e.printStackTrace(); 
            } 
            return str; 
        } 
     
    public static void main(String args[]){ 
        class Node{ 
            int value = 0;// 元素值  
            int dir = -1;// 0 : 左向箭頭，1：有向箭頭  
        } 
        System.out.println("——換位法求全排列———"); 
        System.out.println("—-第一個排列必須有序——"); 
         
        int n = 0;//元素個數  
        boolean flag = true;//從控制臺讀入數據不合法的話，該值一直為true  
        while(flag){ 
            try{ 
                n = Integer.parseInt(readDataFromConsole("請輸入待排序元素個數: ")); 
                flag = false; 
            }catch(Exception e){ 
                System.out.println("請輸入整數."); 
            }    
        } 
        flag = true; 
        ArrayList<Node> nodes = new ArrayList<Node>(n); 
        Node node = null; 
        for(int i = 1;i <= n;i++){//排列初始化  
            node =  new Node(); www.aiwalls.com
            while(flag){ 
                try{ 
                    node.value = Integer.parseInt(readDataFromConsole("請輸入第" + i + "個元素的值: ")); 
                    flag = false; 
                }catch(Exception e){ 
                    System.out.println("請輸入整數."); 
                } 
            } 
            flag = true; 
            node.dir = 0; 
            nodes.add(node); 
            node = null; 
        } 
        for(int i = 0;i < n;i++){ 
            System.out.print(nodes.get(i).value + "\t"); 
        } 
        System.out.println(); 
        int count = 1; 
        while(true){ 
            int j = 0; // 記錄最大活動整數下標  
            int Max = 0; 
            for(int i = 0;i < n;i++){ // 找出最大活動整數  
                if(0 == i && 0 == nodes.get(i).dir){ 
                    Max = Max; 
                }else if(n-1 == i && 1 == nodes.get(i).dir){ /// 此處應該是一次空操作，不可以輕易將Max 置為 0 ********  
                    Max = Max; 
                }else if(0 == nodes.get(i).dir && i>0 && nodes.get(i).value>nodes.get(i – 1).value && nodes.get(i).value>Max){ 
                    Max = nodes.get(i).value; 
                    j = i; 
                }else if(1 == nodes.get(i).dir && i<n-1 && nodes.get(i).value>nodes.get(i + 1).value && nodes.get(i).value > Max){ 
                    Max = nodes.get(i).value; 
                    j = i; 
                }            
            } 
            //cout << endl;  
            //cout << j << " " << Max << endl;  
            if( 0 == Max ) // 沒有活動整數  
                break; 
            if( 0 == nodes.get(j).dir)  // 交換最大整數與其相鄰的數及方向  
            { 
                int temp,dirtemp; 
                temp =nodes.get(j).value; 
                dirtemp=nodes.get(j).dir; 
                nodes.get(j).value=nodes.get(j – 1).value; 
                nodes.get(j).dir=nodes.get(j – 1).dir; 
                nodes.get(j – 1).value=temp; 
                nodes.get(j – 1).dir=dirtemp; 
            } 
            else if( 1 == nodes.get(j).dir) 
            { 
                int temp,dirtemp; 
                temp =nodes.get(j).value; 
                dirtemp=nodes.get(j).dir; 
                nodes.get(j).value=nodes.get(j + 1).value; 
                nodes.get(j).dir=nodes.get(j + 1).dir; 
                nodes.get(j + 1).value=temp; 
                nodes.get(j + 1).dir=dirtemp; 
            } 
            for(int i=0;i<n;i++)//變換比最大活動整數大的數的方向  
            { 
                if(nodes.get(i).value>Max) 
                { 
                    if(0 == nodes.get(i).dir){ 
                        nodes.get(i).dir=1; 
                    }else if(1 == nodes.get(i).dir){ 
                        nodes.get(i).dir=0; 
                    } 
                } 
            } 
            for(int i=0;i<n;i++){ 
                System.out.print(nodes.get(i).value + "\t"); 
            } 
            count++; 
            System.out.println(); 
        } 
        System.out.println("排列總數為：" + count); 
    } 
} 

摘自 qiaoning13256的專欄