转自:https://blog.csdn.net/lemon_tree12138/article/details/50986990
1.使用递归的方法
思想是交换,有n个数的话,先将第一个数安排好,之后再去管理后面的n-1个数,这样递归下去,直到所有的其他数都管理好,那么就是一个排列。
private static void core(int[] array) { int length = array.length; fullArray(array, 0, length - 1); } private static void fullArray(int[] array, int cursor, int end) { if (cursor == end) { System.out.println(Arrays.toString(array)); } else { for (int i = cursor; i <= end; i++) { ArrayUtils.swap(array, cursor, i);#交换 fullArray(array, cursor + 1, end);#管理剩下的数 } } }
但是上面这个代码是有问题的。。。得出来的会有重复的,具体我也没有思考为什么。
主要应该是因为交换了之后,没有对数组进行还原吧!
下面进行了还原:
private static void fullArray(int[] array, int cursor, int end) { if (cursor == end) { System.out.println(Arrays.toString(array)); } else { for (int i = cursor; i <= end; i++) { ArrayUtils.swap(array, cursor, i); fullArray(array, cursor + 1, end); ArrayUtils.swap(array, cursor, i); // 用于对之前交换过的数据进行还原 } } }
2.存在相同元素
判断cursor之后是否存在值相同的元素,如果有的话,那么就不交换了。
3.非递归-基于元素大小
需要知道找到next permutation的方法。
先从右边往左找到下降的点,然后再从右找到最后一个大于它的数,然后交换即可。