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

import java.io.*; 
import java.util.ArrayList; 
 
class Arrangement{ 
     
    public static void main(String args[]){ 
        Arrangement arrangement = null; 
        int num = 0;//要排序的個數  
        boolean flag = true;//標志位,如果用戶輸入的待排序個數不合法,該值一直為true  
        ArrayList<String> strs = new ArrayList<String>(); 
        while(flag){ 
            try{ 
                num = Integer.parseInt(readDataFromConsole("請輸入待排序的個數:")); 
                flag = false; 
            }catch(Exception e){ 
                System.out.println("請輸入整數."); 
            } 
        } 
        for(int i = 1; i <= num; i ++){ 
            strs.add(readDataFromConsole("請輸入第" + i + "個字符: "));  
        } 
        arrangement = new Arrangement(strs.toArray(new String[]{})); 
        System.out.println("排列後的數據為:"); 
        arrangement.sort(); 
    } 
     
    private String[] str = null; 
     
    public Arrangement(String[] s){ 
        this.str = s; 
    } 
    //從控制臺讀入數據  
    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; 
        } 
     
    private void sort(){ 
        int num=str.length; 
         
        int[] n1 = new int[num -1]; 
        int[] nss = new int[num]; 
        String[] s = new String[num]; 
         
        boolean flag = false; 
        int x = 0; 
         
        do{ 
            if(x == 0){//第一遍初始化  
                for(int i = 0;i < num – 1;i ++){ 
                    n1[i] = 0; 
                } 
            } else {//生成序數  
                for(int i = 0;i < num – 1;i ++){ 
                    if(n1[num – 2 – i] < i + 1){ 
                        n1[num – 2 – i] ++; 
                        for(int j=num-1-i;j<num-1;j++){ 
                            n1[j] = 0; 
                        } 
                        break; 
                    } 
                } 
            } 
            for(int i = 0;i < num – 1;i++){ 
                if(n1[i] == (num – 1 – i)){ 
                    flag = false; 
                } else { 
                    flag = true; 
                    break; 
                } 
            } 
            for(int i = 0;i < num;i++){//標記位賦初值  
                nss[i] = 0; 
            } 
            for(int i = 0;i < num – 1;i++){//計算排列順序並為排列後的賦值  
                int hh = 0, j = 0;//記錄前邊總共移動的位數  www.aiwalls.com
                do{ 
                    if(nss[num – 1 – hh] == 1){ 
                        hh++; 
                        continue; 
                    } else { 
                        if(j == n1[i]){ 
                            break;//每個字母距最右端未填入的位置  
                        } else { 
                            hh++; 
                            j++; 
                        } 
                    } 
                } while(true); 
                hh = num – 1 – hh; 
                s[hh] = str[num-1-i]; 
                nss[hh] = 1; 
            } 
            for(int i = 0; i < num;i++){//查找空缺位  
                if(nss[i] == 0) { 
                    s[i] = str[0]; 
                    break; 
                } 
            } 
            System.out.print(++x + "\t"); 
            for(int i = 0;i < num – 1;i++){ 
                System.out.print(n1[i] + ""); 
            } 
            System.out.print("\t"); 
            for(int i = 0;i < num;i++){ 
                System.out.print(s[i] + ""); 
            } 
            System.out.println(); 
        }while(flag); 
    } 

摘自 qiaoning13256的專欄

發佈留言