0前言
今天在线笔试遇见了一个很有意思的编程题，特此整理记录如下：
1.问题描述
问题描述（大概意思是）
给出一组整数(整数范围是1-9，数据不重复)，要求按升序输出所有的排序可能性
输入：首先输入一个n表示数据个数，然后是n个整数
输出：按升序一次输出每一种结果
例如：
输入 ：
3
1 5 9
输出
159
195
519
591
915
951
2.问题分析
根据题意不难将问题分解成：
1.找出所有的排序可能性
2.将所有的结果进行排序
2.1 找出所有的排序可能性
所有的排序可能性，即模拟全排列
根据已知知识点，可知所有可能性的个数为：
全排列个数
问题的关键点就在于，如何模拟出所有的可能性
首先，拿例子1 5 9来说
159
195
第一个位置与第一个位置交换，然后保持第一个位置不变，第二个位置与第三个位置交换
519
591
第二个位置与第一个位置交换，然后保持第一个位置不变， 第二个位置与第三个位置交换
915
951
第三个位置与第一个位置交换，然后保持第一个位置不变， 第二个位置与第三个位置交换
如果n个元素，就是n组，每组再递归处理
结论:
全排列就是从第一个元素起分别与它后面的元素交换所形成的集体
2.2排序
因为已知整数范围为1-9，则可以将所有的整数拼接成一个字符串，然后按照字符串排序即可
3.代码实现
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
/**
* @Title:Main.java
* @author Stone6762
* @CreationTime 2018年6月11日 下午9:25:46
* @Description:
*/
public class Main {
/** @list存储全排列的所有可能性
*/
public static List<String> list;
public static void permutation(int[] array, int index) {
if (index > array.length) {
return;
}
if (index == array.length) {
StringBuilder b = new StringBuilder();
for (int i = 0; i < array.length; i++) {
b.append("" + array[i]);
}
list.add(b.toString());
}
for (int i = index; i < array.length; i++) {
swap(array, index, i);
permutation(array, index + 1);
swap(array, index, i); // 再次交换，保持原状
}
}
private static void swap(int[] array, int index, int target) {
int tmp = array[index];
array[index] = array[target];
array[target] = tmp;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
int n = scan.nextInt();
int array[] = new int[n];
for (int i = 0; i < array.length; i++) {
array[i] = scan.nextInt();
}
list = new ArrayList<String>();
permutation(array, 0);
Collections.sort(list);
for (String str : list) {
System.out.println(str);
}
}
}
}
