練習 － Arrangement

Arrangement

題目：列出正整數n，則1到n這n個數可以構成n!種排列，把這些排列按照從小到大的順序列出，如n=3時，列出123，132，213，231，312，321六個排列。請列出某個排列，求出這個排列的下k個排列，如果遇到最後一個排列，則下一個排列為第1個排列，即排列1 2 3 ⋯n。 例如：n=3，k=2列出排列2 3 1，則它的下一個排列為3 1 2，下兩個排列為3 2 1，因此答案為3 2 1。

輸入：第一行是一個正整數m，表示測試資料的個數，下面是m組測試資料，每組測試資料第一行是兩個正整數n和k，第二行有n個正整數，是1 2 ⋯n的一個排列。

輸出：對於每組輸入資料，輸出一行，n個數，中間用空格隔開，表示輸入排列的下k個排列。

import java.util.Scanner;

public class Arrangement {

	public static boolean compare(int x, int y) { // 比較兩個數字的大小
		if (x < y) {
			return true;
		}

		return false;
	}

	public static void main(String[] args) {
		Scanner scanIn = new Scanner(System.in); // 輸入需要測試的資料組數
		int count = scanIn.nextInt();

		for (int x = 0; x < count; x++) {
			scanIn = new Scanner(System.in);
			int n = scanIn.nextInt(); // n為排列陣列內的整數個數
			int k = scanIn.nextInt(); // 第k個排列

			scanIn = new Scanner(System.in);
			int array[] = new int[n];
			for (int y = 0; y < n; y++) {
				array[y] = scanIn.nextInt(); // 排列陣列
			}

			for (int z = 0; z < k; z++) {
				int tempArrangePos = 0;
				for (int i = n - 1; i > 0; i--) { // 由左至右找第1個非遞增的數字
					int a = array[i - 1];
					int b = array[i];
					if (a < b) {
						int minVal = b;
						int minPos = i;
						for (int j = i; j < n; j++) { // 找到第1個非遞增數字後，再找出右方大於它的最小數
							int c = array[j];
							if (a < array[j] && c < minVal) {
								minPos = j;
							}
						}
						// 將第1個非遞增數字和右方大於它的最小數交換位置
						int temp = array[i - 1];
						array[i - 1] = array[minPos];
						array[minPos] = temp;
						tempArrangePos = i;
						break;
					}
				}
				for (int m = 0; m < n - 1; m++) { // 將第1個非遞增數字的右方所有數字按遞增排序
					for (int l = tempArrangePos; l < n - m - 1; l++) {
						if (!compare(array[l], array[l + 1])) {
							int temp = array[l];
							array[l] = array[l + 1];
							array[l + 1] = temp;
						}
					}
				}
			}

			for (int p = 0; p < n; p++) {
				System.out.print(array[p] + " ");
			}
			System.out.println("");
		}
	}

}