把数组做成全数组是个常见的问题。 如果是喜欢测试算法的公司(一些大公司似乎喜欢测试算法)，我想会考察申请者这个全数组的问题(即使不让我写完整的代码，我也会让你说明大致的想法)。 这个问题也很难，说容易就容易，所以这里试着对这个问题进行更全面的分析吧。 如果有遗漏的话，请指出来。
版权说明作者所有。
商业转载请联系作者取得许可。 非商业转载请注明出处。
作者： Coding-Naga
发布日期： 2016年3月27日
本文链接： http://blog.csdn.net/lemon _ tree 12138/article/details/50986990
来源： CSDN
其他内容：分类算法和数学
请设计一种算法，为特定数组a=[a1，a2，a3，an]输出该数组的所有排列方式。
例如，a=[1、2、3]
输出功率
[1、2、3][1、3、2][2、1、3][2、3、1][3、2、1][3、1、2]从小到大顺序输出的情况下？ 算法怎么写？
根据递归实现思路分析表明，所有数组的含义是一个数组的所有可排序性。 那么，现在让我们做这样的假设吧。 假设给定的几个数组中第一位不同，则可以认为这些数组并不一定是同一数组。 这是一个明显的问题。 有了以上的结论，同样，第一位相同，第二位不同，在这些序列中也一定不是相同的序列，从以上的结论可以得出。
那么，这个问题可以这样看。 在获得初始位置的所有情况之后，提取序列t的第一位置，剩馀的序列可以被认为是全新的序列T1，序列T1可以被认为与先前的序列无关。 同样，我们可以对这个T1进行与t相同的操作，直到t中只有一个元素。 这样我们就得到了所有的可能性。 所以很明显，这是递归算法。
例如，下图显示了将第一个元素与其所有其他元素交换的图像。
从那里提取第I个元素，对剩下的元素进行上图的交换操作，如下所示。
所有的元素都不相同，这基于上述分析，我们知道这可以递归实现。 实现代码如下：
私有状态语音核心(int [ ] array ) { int length=array.length； 全阵列(阵列，0，长度-1)； }专用staticvoidfullarray (int [ ] array，int cursor，int end ) if ) cursor==end ) system.out.println (arrays ) ) }else{for(intI=cursor； i=end； I ) Arrayutils.swap(Array，cursor，I )； 全阵列(阵列，cursor 1，end )； }}运行结果
[ 1，2，3 ] [ 1，3，2 ] [ 3，1，2 ] [ 3，2，1 ] [ 1，2，3 ] [ 1，3，2 ]这个答案有些不可思议。 为什么有几个小组重复呢？ 为什么第一名中没有2？
理论上，上述代码没有问题。 因为在序列中的每个位循环时，后续序列的递归操作可能会继续。 core ()方法当然没有问题。 问题在于fullArray ) )方法。 很容易就被那个for循环锁定了。 仔细推敲一下循环体中的代码吧。 替换数组后，将替换的数组放入了下一个递归中，第一个元素除外。 递归结束后又进入下一个循环。 这是某个循环程序做的工作，这里有问题。 那就是进入下一个周期时序列发生了改变。 但是，如果我们假设第一位的所有可能性，那么这些序列的初始状态必须一致。
那么，这样就发现了问题。 我们需要保证序列进入下一个周期时的状态一致性。 保证的方法是恢复序列。 我们将fullArray ()修改如下。
专用staticvoidfullarray (int [ ] array，int cursor，int end ) if ) cursor==end ) system.out.println ) Arrays.end i=end； I ) Arrayutils.swap(Array，cursor，I )；
fullArray(array, cursor + 1, end); ArrayUtils.swap(array, cursor, i); // 用于对之前交换过的数据进行还原 } } }修改后的运行结果
[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 2, 1][3, 1, 2] 存在相同元素的情况上面的程序乍一看没有任何问题了。可是，如果我们对序列进行一下修改 array = {1, 2, 2}.我们看看运行的结果会怎么样。
[1, 2, 2][1, 2, 2][2, 1, 2][2, 2, 1][2, 2, 1][2, 1, 2]这里出现了好多的重复。重复的原因当然是因为我们列举了所有位置上的可能性，而没有太多地关注其真实的数值。
现在，我们这样来思考一下，如果有一个序列T = {a1, a2, a3, …, ai, … , aj, … , an}。其中，a[i] = a[j]。那么是不是就可以说，在a[i]上，只要进行一次交换就可以了，a[j]可以直接忽略不计了。好了，基于这样一个思路，我们对程序进行一些改进。我们每一次交换递归之前对元素进行检查，如果这个元素在后面还存在数值相同的元素，那么我们就可以跳过进行下一次循环递归（当然你也可以反着来检查某个元素之前是不是相同的元素）。
基于这个思路，不难写出改进的代码。如下：
由于非递归的方法是基于对元素大小关系进行比较而实现的，所以这里暂时不考虑存在相同数据的情况。
在没有相同元素的情况下，任何不同顺序的序列都不可能相同。不同的序列就一定会有大有小。也就是说，我们只要对序列按照一定的大小关系，找到某一个序列的下一个序列。那从最小的一个序列找起，直到找到最大的序列为止，那么就算找到了所有的元素了。
好了，现在整体思路是清晰了。可是，要怎么找到这里说的下一个序列呢？这个下一个序列有什么性质呢？
T[i]下一个序列T[i+1]是在所有序列中比T[i]大，且相邻的序列。关于怎么找到这个元素，我们还是从一个例子来入手吧。
现在假设序列T[i] = {6, 4, 2, 8, 3, 1}，那么我们可以通过如下两步找到它的下一个序列。
看完上面的两个步骤，不知道大家有没有理解。如果不理解，那么不理解的点可能就在于替换点和被替点的寻找，以及之后为什么又要进行反转上。我们一个一个地解决问题吧。
这样，思路已经完全梳理完了，现在就是对其的实现了。只是为了防止给定的序列不是最小的，那就需要对其进行按从小到大进行排序。 逻辑实现 public class DemoFullArray2 { public static void main(String[] args) { int[] array = {2, 3, 1, 4}; core(array); } private static void core(int[] array) { // 先排序 SortUtils sortUtils = new SortUtils(new QKSort()); sortUtils.sort(array); System.out.println(Arrays.toString(array)); // 最初始的序列 do { nextArray(array); System.out.println(Arrays.toString(array)); } while (!isLast(array)); } private static int[] nextArray(int[] array) { int length = array.length; // 寻找替换点 int cursor = 0; for (int i = length - 1; i >= 1; i--) { // 找到第一个递增的元素对 if (array[i - 1] < array[i]) { cursor = i - 1; // 找到替换点 break; } } // 寻找在替换点后面的次小元素 int biggerCursor = cursor + 1; for (int i = cursor + 1; i < length; i++) { if (array[cursor] < array[i] && array[i] < array[biggerCursor]) { biggerCursor = i; } } // 交换 ArrayUtils.swap(array, cursor, biggerCursor); // 对替换点之后的序列进行反转 reverse(array, cursor); return array; } private static void reverse(int[] array, int cursor) { int end = array.length - 1; for (int i = cursor + 1; i <= end; i++, end--) { ArrayUtils.swap(array, i, end); } } private static boolean isLast(int[] array) { int length = array.length; for (int i = 1; i < length; i++) { if (array[i - 1] < array[i]) { return false; } } return true; }} Ref http://blog.csdn.net/morewindows/article/details/7370155
转载于:https://www.cnblogs.com/fengju/p/6336002.html