交換相鄰法（2）

通過上篇文章可以看到，如果想要生成{1,2.....,n}的全排列，那麼在生成的過程中我們需要将{1} {1,2} {1,2,3} ...... {1,2,3.....n}的排列進行儲存。那麼如何才能做到，排列覆寫目前排列而不必保留所有排列呢？

Even 給出一種描述如下：

生成{1,2,.....n}的排列算法

從1,2,3，n開始（<---  每一個數字都需要加上方向）

可移動：當數字指向方向上的相鄰數字比該數字小時那麼表示該數字可以移動。當然當處于集合開始，或者結尾，并且方向是向左或者向右時是不可移動的。

（1）求出最大的可移動整數m

（2）交換m和它的箭頭所指的方向的與它相鄰的整數

（3）交換所有滿足p>m的整數p上的箭頭的方向。（m經過交換後變成不可移動，然後找到次大來代替m，此時将m重新指派，那麼必然有原始的值大于目前m此整數便是p)

import java.util.Arrays;


public class DirectionSortArray {
	Number[] numbers; 
	
	public class Number{
		int index;
		int value;
		Direction direction;
	}
	enum Direction{
		left,right
	}
	public String arrayToString(Number[] numbers){
		int[] temp = new int[numbers.length];
		int i = 0;
		for(Number number : numbers){
			temp[i++] = number.value;
		}
		return Arrays.toString(temp);
	}
	public Number getBiggest(Number[] numbers){
		Number temp = null;
		for(int i = 0;i < numbers.length;i++){
			if(isMoveable(numbers[i],i,numbers) && (temp == null || temp.value < numbers[i].value)){
				temp = numbers[i];
			}
		}
		return temp;
	}
	public boolean isMoveable(Number number,int index,Number[] numbers){
		if(index == numbers.length - 1 && number.direction == Direction.right){
			return false;
		}else if(index == 0 && number.direction == Direction.left){
			return false;
		}else{
			Number nextNumber = null;
			if(number.direction == Direction.left){
				nextNumber = numbers[index - 1];
			}else{
				nextNumber = numbers[index + 1];
			}	
			if(nextNumber.value > number.value){
				return false;
			}
		}
		return true;
	}
	//進行交換
	public void swap(Number bigNumber,Number[] numbers){
		//直接進行交換
		int changedIndex = 0;
		if(bigNumber.direction == Direction.right){
			changedIndex = bigNumber.index + 1;
		}else if(bigNumber.direction == Direction.left){
			changedIndex = bigNumber.index - 1;
		}
		numbers[bigNumber.index] = numbers[changedIndex];
		numbers[bigNumber.index].index = bigNumber.index;
		numbers[changedIndex] = bigNumber;
		numbers[changedIndex].index = changedIndex;
		
		bigNumber.index = changedIndex;
		//判斷目前Number是否可移動
		if(!isMoveable(bigNumber, changedIndex,numbers)){
			//不可移動時找到次大值，交換方向後，将比它大的所有數字方向進行變換
			bigNumber = getBiggest(numbers);
			if(bigNumber == null){
				return;
			}
			System.out.println(arrayToString(numbers));
			changeDirection(bigNumber,numbers);
			//進行一次交換
			swap(bigNumber,numbers);
			
		}
	}
	public void changeDirection(Number number,Number[] numbers){
		for(Number temp : numbers){
			if(temp.value > number.value){
				if(temp.direction == Direction.left){
					temp.direction = Direction.right;
				}else{
					temp.direction = Direction.left;
				}
			}
		}
	}
	//初始化資料
	public void init(){
		numbers =  new Number[4];
		for(int i = 0;i < numbers.length;i++){
			numbers[i] = new Number();
			numbers[i].direction = Direction.left;
			numbers[i].value = i + 1;
			numbers[i].index = i;
		}
	}
	//進行排序
	public void sort(){
		Number bigNumber = getBiggest(numbers);
		while(bigNumber != null){
			System.out.println(arrayToString(numbers));
			//找出最大的number
			swap(bigNumber, numbers);
			bigNumber = getBiggest(numbers);
		}
		System.out.println(arrayToString(numbers));
	}
	
	public static void main(String[] args) {
		DirectionSortArray array = new DirectionSortArray();
		array.init();
		array.sort();
	}
}