練習 - 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("");
		}
	}

}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

*

驗證碼 * Time limit is exhausted. Please reload CAPTCHA.

這個網站採用 Akismet 服務減少垃圾留言。進一步了解 Akismet 如何處理網站訪客的留言資料