递归法----元素全排列问题

问题描述:设R={r1,r2,r3,…,r n}时要进行排列的n个元素(不考虑相等情况),写出一个算法,列出R的所有不同排列。

算法设计:给定n及待排列的n个元素。计算出这n个元素的所有不同排列。

算法思路:设R={r1,r2,r3,…,r n}是要进行排列的n个元素,R i = R - {r i}。集合X中元素的全排列标记为Perem(X)。(r i)Perem(X)表示在全排列Perem(X)的每一个排列前加上前缀 r i 得到的排列。R的全排列可归纳定义如下:

  • 当n = 1 时,Perem(R) = (r),其中r是集合R中唯一的元素。
  • 当n > 1 时,Perem(R) 由(r1)Perem(R1), (r2)Perem(R2), ... ,(r n)Perem(R n)构成。

通俗解释:用自己的话说就是,元素的全排列相当于 集合中每一个元素居首位且其余元素全排列 的和。而其中元素的全排列 又可以理解为其余元素这个集合中 每一个元素居首位且其余元素全排列 的和这种情况,即是更小一个规模的全排列。而当其余元素只有一个时,排列唯一,逆向退回去,排列顺序也就都有了。

 1 package com.school.blog;
 2 
 3 /**
 4  * 全排列问题,写出一个集合中元素的所有排列情况
 5  * @author AganRun
 6  */
 7 public class WholeSort {
 8 
 9     static int sum = 0;        //记录排列总数(验证方式是n!)
10     
11     public static void main(String[] args) {
12         
13         char[] a = { 'a', 'b', 'c', 'd'};    //举此情况为例,用户也可以自行输入
14         perm(a, 0, a.length - 1);
15         System.out.println("共有" + sum + "种全排列");
16     }
17 
18     //全排列函数,将List字符数组中从k到m进行全排列
19     public static void perm(char[] list, int k, int m) {
20         
21         if(k == m){        //待排列只有一个元素
22             for(int i=0; i<=m; i++){
23                 System.out.print(list[i]);
24             }
25             sum++;
26             System.out.println();
27         }else{            //进入小一个规模的全排列
28             for(int i=k; i<=m; i++){
29                 swap(list, i, k);    //每一个元素居首位,全排列其余元素
30                 perm(list, k+1, m);
31                 swap(list, i, k);
32             }
33         }
34     }
35     
36     //将list数组中的元素list[k]和list[i]交换位置
37     public static void swap(char[] list, int k, int i){
38         char a = list[k];
39         list[k] = list[i];
40         list[i] = a;
41     }
42 
43 }
原文地址:https://www.cnblogs.com/AganRun/p/6601996.html