全排列的打印

绝地灬酷狼 2022-03-22 04:29 155阅读 0赞

## 题目:给定几个不重复数字,请输出全排列 ##

示例:1,2,3  
输出:1,2,3  
1,3,2  
2,1,3  
2,3,1  
3,2,1  
3,1,2  
思考:给定的字符是1,2,3,…n  
全排列会允许任一字符能到达任一位置  
比如:1,2,3  
如果固定 1为第一个字符,则需要对 2,3 进行全排列  
如果固定 2为第一个字符,则需要对 1,3 进行全排列(为什么不是3,1被?这里是将1与2位置交换,方便思考,以免混乱)  
如果固定 3位第一个字符,则需要对 2,1 进行全排列

也就是说:  
给定k=0,k及其之后任意元素交换到位置k,此时输出都是一个全排列  
k不断增加,直到k=数组长度,则表示已经尝试了所有的全排列  
似乎就可以使用递归了,固定某一段位置,对剩下部分求全排列

/** * @author wangwei * @date 2019/1/25 20:43 * @classDescription 打印n个数的全排列:每个元素都可以放到位置k, k 初始化为0,k之后的元素都可以交换到位置k, * 每个元素都可以放到k+1, * 知道k位于最后一个位置,表示已经处理完,可以输出 * 比如输入 3 * 输出:1,2,3 * 1,3,2 * 2,1,3 * 2,3,1 * 3,2,1 * 3,1,2 */
    public class FullPermutation { 
        public static void print(int array[],int k){ 
            if(k==array.length-1){ 
                for(int i=0;i<array.length;i++){ 
                    System.out.print(array[i]+" ");
                }
                System.out.println();
                return;
            }
         
         
            for(int i=k;i<array.length;i++){ 
    
                ArrayUtil.swap(array,k,i);
                print(array,k+1);
                ArrayUtil.swap(array,k,i);
             
            }
    
        }
    
        public static void main(String[] args) { 
            int [] array=new int[]{ 1,2,3};
            print(array,0);
        }
        /** * 思考:如果有重复元素,那么怎么输出所有的全排列呢? * 需要记录与当前k交换的元素值,如果同一种元素交换到k位置过,那么就不再交换 */
    }

测试效果:输入 1,2,3  
输出:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTIyOTI3_size_16_color_FFFFFF_t_70]

## 变式:给定几个数字(可能重复),请输出全排列 ##

示例:1,2^,2  
输出:1,2^,2 (姑且认为2是不一样的) 这里是1与1交换  
1,2,2^ (重复) ----- 2^与2交换  
2,2^,1 - ---- 1与2交换  
2,1,2^ ----- 2^与1交换  
2^,1,2(重复) ----- 1与2^ 交换  
2^,2,1(重复) ------ 1与2交换  
**重复元素怎么处理呢??**  
标记已经交换过的元素,如果交换过,则不再交换

public static void print(int array[],int k){ 
            if(k==array.length-1){ 
                for(int i=0;i<array.length;i++){ 
                    System.out.print(array[i]+" ");
                }
                System.out.println();
                return;
            }
            //
          boolean[] record=new boolean[1024];//记录交换的数据
            for(int i=k;i<array.length;i++){ 
                if(record[array[i]]){ 
                   continue;//有交换记录,跳过此次交换
               }
                ArrayUtil.swap(array,k,i);
                print(array,k+1);
                ArrayUtil.swap(array,k,i);
               record[array[i]]=true;
            }
    
        }

测试效果:  
1,2,2  
输出:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTIyOTI3_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTIyOTI3_size_16_color_FFFFFF_t_70]: /images/20220322/2f5f7fd5b12f4755ba6a294f0171662f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2OTIyOTI3_size_16_color_FFFFFF_t_70 1]: /images/20220322/72ef09a24ceb4cabbf13a0396601e88f.png