字符串全排列算法-非递归实现

//前提：字符串序列是数字组成，且升序排列
/*算法说明:
起点：字典序最小的排列，例如12345
终点：字典序最大的排列，例如54321
过程：从当前排列生成字典序刚好比它大的下一个排列

过程化：整理成算法语言
步骤：后找、小大、交换、翻转——
后找、查找：从倒数第二位开始作为基础位置，找基础位置后的比基础位置上的数大的且最小的数
交换：交换基础位置上的数 和 找到的比基础位置大的最小的数
翻转：将基础位置之后的数反转。因为此时基础位置后的数一定是降序的，要让它成为升序

与我的上一个代码段：字符串全排列算法-递归实现 区别：
上一个代码段没有处理有重复数字的全排列，如1223，递归则会有重复的排列。而非递归实现，天生免疫重复数字
*/

代码：
	/*有序序列的全排列算法*/
	void allSequence(char[] s){
		System.out.println(s);//初始打印
		boolean isEnd = false;
		/*如果有找到可交换的位置，则可以进行下一次；否则完成全排序*/
		while(!isEnd){
			int[] fromAndToIndex = getSwapFromAndToIndex(s);
			if(fromAndToIndex != null){
				swapChar(s,fromAndToIndex[1],fromAndToIndex[0]);
				revertStr(s,fromAndToIndex[0]+1);//反转from右边的数，即右边的数从小到大排序
				System.out.println(s);
			}else{
				isEnd = true;
			}
		}
	}
	
	/**
	 * 获得字符串序列中两个交换位置，这两个位置上的数交换后，可以增大该字符串序列。这里获得的就是能最小增大的两个交换位置。
	 * 例如：1342，那么找两个位置上的数交换后能让他增大。那基础位置就可以从倒数第二个数开始，然后从基础位置往后找，
	 * 	若找到比基础位置上的数大的数，那此时交换两个数就能增大这个序列。并且要找到比基础位置上的数大并且是所有比它大的最小的数
	 * @param str
	 * @return 返回的int[2]数组元素。0位置元素记录交换的左边位置，1位置元素记录交换的右边位置 
	 */
	int[] getSwapFromAndToIndex(char[] str){
		int[] fromAndTo = new int[2];	//fromAndTo[0]记录基础位置
		int basis = str.length - 2;		//基础位置
		int afterBasis = basis + 1;		//可交换位置	
		fromAndTo[1] = -1;
		while(basis >= 0){
			if(str[basis] < str[afterBasis]){
				if(fromAndTo[1] < 0 || (fromAndTo[1] > 0 && str[fromAndTo[1]] > str[afterBasis])){
					fromAndTo[1] = afterBasis;
				}
			}
			if(++afterBasis > str.length - 1){
				if(fromAndTo[1] < 0){
					basis--;
					afterBasis = basis + 1;
					fromAndTo[1] = -1;
				}else{
					fromAndTo[0] = basis;
					return fromAndTo;
				}
			}
		}
		return null;
	}
	
	void swapChar(char[] s, int i, int j) {
		char temp = s[i];
		s[i] = s[j];
		s[j] = temp;
	}
	
	/**反转。把字符数组从from位置开始后的数反转*/
	void revertStr(char[] str, int from){
		if(str.length - from <= 1){
			return;
		}
		for(int i = from; i < (str.length + from)/2;i++){
			swapChar(str,i,str.length - 1 -(i - from));
		}
	}

    //测试
    public static void main(String[] args) {
        StrRemove s1 = new StrRemove();
        String waitList1 = "123";
        String waitList2 = "1223";	
        s1.allSequence(waitList1.toCharArray());
        System.out.println("-------------------------------------");
        s1.allSequence(waitList2.toCharArray());
	}

 //测试结果：
123
132
213
231
312
321
-------------------------------------
1223
1232
1322
2213
2231
2312
2321
3122
3221