import java.util.ArrayList;

import java.util.List;



public class StringSort {



	/**

	 * 问题:一个由不重复数字组成的字符串，输出他们的全组合，并且是按从小到大的顺序输出

	 * 解决方案2：先找到最小的一个数，然后依次找到更大一点的数

	 * 1234从右边开始往左找，当第一次找到左边小于右边的时候就交换位置，这样就能保证是最小的增长 1243

	 * 1243--->2和4不能直接交换，要从右开始重新找，找到第一个比2大的数3-->13-42，把剩下的数排序,从小到大 --> 1324（目标）

	 * 然后按上面规则--->1342（目标）-->14-32--后面的排序--->1423（目标） 然后再照上--->1432

	 * （目标）--->.2431....-->4132--->后面排序---->4123（目标）

	 * XXXXX---->4132（目标）--->4312--->排序---->4312（目标） XXXXX---->4321（目标）----完成

	 * 

	 * @param args

	 */

	private static ArrayList<String> list = new ArrayList<String>();



	// 

	public static void main(String[] args) {

		String[] data = { "1", "3", "4","2" };

		findMin(data);

		System.out.println();

		sort(list);

	}



	// 1 2 3 4

	private static void sort(ArrayList<String> list2) {

		for (int i = list2.size() - 1; i > 0; i--) {

			if (Integer.parseInt(list2.get(i - 1)) < Integer.parseInt(list2

					.get(i))) {

				for (int k = list2.size() - 1; k > i - 1; k--) {

					if (Integer.parseInt(list2.get(k)) > Integer.parseInt(list2

							.get(i - 1))) {

						list2 = swap(k, i - 1, list2);

						break;

					}

				}

				list2 = sortList(list2, i);

				for (int j = 0; j < list2.size(); j++) {

					System.out.print(list2.get(j));

				}

				System.out.println();

				sort(list2);

			}

		}

	}



	/** 将list中第N项后的从小到大排序 */

	private static ArrayList<String> sortList(List<String> list3, int n) {

		ArrayList<String> arr = new ArrayList<String>(list3);

		for (int i = n; i < arr.size() - 1; i++) {

			for (int j = i + 1; j <= arr.size() - 1; j++) {

				if (Integer.parseInt(arr.get(i)) > Integer.parseInt(arr.get(j))) {

					String temp = arr.get(i);

					arr.set(i, arr.get(j));

					arr.set(j, temp);

				}

			}

		}

		return arr;

	}



	/** 返回交换后的新的数组 */

	private static ArrayList<String> swap(int a, int b, ArrayList<String> list2) {

		String temp = list2.get(a);

		list2.set(a, list2.get(b));

		list2.set(b, temp);

		return list2;



	}



	/** 找到最小的组合 */

	private static void findMin(String[] data) {

		for (int i = 0; i < data.length - 1; i++) {

			for (int j = 0; j < data.length - i - 1; j++) {

				int a = Integer.parseInt(data[j]);

				int b = Integer.parseInt(data[j + 1]);

				if (a > b) {

					String temp = data[j];

					data[j] = data[j + 1];

					data[j + 1] = temp;

				}