通过分治思想递归实现数组的全排列

心已赠人 2022-04-22 05:44 159阅读 0赞

在高中数学学习排列与组合的时候，我们知道，要得到一组元素的所有排列情况例如【1，2，3，4，5】这五个数字，它所有的排列一共有5！种，也就是5x4x3x2x1=120种。  
        这是怎么得来的呢？我们是将它看作一个长度为5的序列，将每个位置上的可选元素的数目相乘得到的。例如，第一个数可以从1~5中选择，可选元素是5个，去掉第一位选中的元素，第二位可选元素有4个，以此类推，一共有120种排列方式。  
        我们在编程中借鉴这个过程：数组第一个数和其他所有的数交换位置，可以得到数组第一个数可能出现的所有排列情况；然后先忽略掉数组第一位数字，将剩余数组视作一个新的数组，新数组的第一个数字再和其他所有数字交换位置，可以得到新数组第一个数可能出现的所有排列情况，以此类推，将一个数组分治为越来越小的数组，最后组合出来的排列，就是原数组的全排列。

--------------------

/** * 分治递归实现全排列 * * @author liuxiaofeng * @date 2018/10/24 13:32 */
    public class PermutationTest { 
    
        /** * 记录排列数 */
        private int count = 0;
    
    
        /** * 直接传入数组的重载方法 * * @param arr 进行排列的数组 */
        private void permutation(char[] arr) { 
            permutation(arr, 0, arr.length - 1);
        }
    
    
        /** * 进行全排列的方法 * * @param arr 字符数组 * @param start 数组开始索引（分治子数组的起始索引） * @param end 数组末尾索引（为减少调用length方法次数，将末尾索引值静态化） */
        private void permutation(char[] arr, int start, int end) { 
            if (start == end) { 
                //排列完成，打印数组
                System.out.println("第 " + (++count) + " 个排列：" + Arrays.toString(arr));
            } else { 
                for (int i = start; i < arr.length; i++) { 
                    //如果当前字符之前未出现过(非重复字符)，和其他字符位置进行交换
                    if (isUnique(arr, start, i)) { 
                        //将当前字符与其他字符交换位置
                        swap(arr, start, i);
    
                        //将当前字符之后的部分视作新的数组（分治），对其进行排列
                        permutation(arr, start + 1, end);
    
                        //一次循环结束后还原字符位置，开始下一次循环
                        swap(arr, start, i);
                    }
                }
            }
        }
    
    
        /** * 字符交换位置的方法 * * @param arr 字符数组 * @param index1 索引1 * @param index2 索引2 */
        private void swap(char[] arr, int index1, int index2) { 
            char tmp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = tmp;
        }
    
    
        /** * 判断当前字符是否已经出现过，出现过就是已经交换过，不再进行交换 * * @param arr 字符数组 * @param start 当前数组第一个字符的索引 * @param curr 当前字符索引 * @return 当前字符是否需要进行交换 */
        private boolean isUnique(char[] arr, int start, int curr) { 
            for (int i = start; i < curr; i++) { 
                if (arr[curr] == arr[i]) { 
                    //当前字符已经出现过，返回false
                    return false;
                }
            }
            return true;
        }
    
    
        /** * 测试方法 */
        @Test
        public void test() { 
            char[] arr = "1268133".toCharArray();
            permutation(arr);
        }
    }