AllPermutation列举全排列

由于在排版系统中的需要今天写了一个可以列举出全排列的AllPermutation类(主要是按照字典序的顺序)：

 

import java.util.Arrays;

public class AllPermutation
{
	int elements[];

	public AllPermutation(int[] elements)
	{
		super();
		this.elements = elements;
	}

	public int[] next()//according to the order of dictionary
	{

		int posA = -1;
		for (int i = elements.length - 1; i >= 1; i--)
		{
			if (elements[i] > elements[i - 1])
			{
				posA = i - 1;
				break;
			}
		}
		if (posA == -1)//is the biggest
		{
			System.out.println("no more permutaion!");
			return null;
		}

		int posB = posA + 1;//save another position
		for (int j = elements.length - 1; j >= posB; j--)
		{
			if (elements[j] > elements[posA] && elements[j] < elements[posB])
			{
				posB = j;
			}
		}
		swap(posA, posB);
		Arrays.sort(elements, posA + 1, elements.length);//ascending sort

		int[] next = new int[elements.length];
		System.arraycopy(elements, 0, next, 0, elements.length);//copy
		return next;
	}

	private void swap(int i, int j)
	{
		// TODO Auto-generated method stub
		int temp = elements[i];
		elements[i] = elements[j];
		elements[j] = temp;
	}
}

 

使用时：

 

		AllPermutation permutation =new AllPermutation(new int[]{1,2,3,4});
		int[] temp=null;
		while((temp=permutation.next())!=null)
		{
			for (int index = 0; index < temp.length; index++)
			{
				int j = temp[index];
				System.out.print(j+",");
			}
			System.out.println("");
		}

 

 

输出结果 写道

1,2,4,3,
1,3,2,4,
1,3,4,2,
1,4,2,3,
1,4,3,2,
2,1,3,4,
2,1,4,3,
2,3,1,4,
2,3,4,1,
2,4,1,3,
2,4,3,1,
3,1,2,4,
3,1,4,2,
3,2,1,4,
3,2,4,1,
3,4,1,2,
3,4,2,1,
4,1,2,3,
4,1,3,2,
4,2,1,3,
4,2,3,1,
4,3,1,2,
4,3,2,1,
no more permutaion!