[Java] UVa 10098 Generating Fast, Sorted Permutation

題目連結

題意:
每組測資給定一個字串(長度最多10)，要按順序列出所有相異的 Permutation
所謂的 permutation 指的是某個字串的一種排序方式
組成相同，但順序不同

例如: 字串 ABC，他的 permutation 有:
ABC, ACB, BAC, BCA, CAB, CBA
總共會有3! (3階乘) = 6種

題目要求按照字母順序從頭到尾輸出
像是給定 BCA ，其 permutation 與上述的ABC相同

輸出如下:
ABC
ACB
BAC
BCA
CAB
CBA

解法:
解題關鍵就是要找到所有permutation
而且必須是按字母順序

在C++的STL當中
似乎有相關方法可以呼叫(next_permutation)
不過Java沒有
所以我們必須自行實作
觀察找出下一個 permutation 的規律

規律如下:
以ABCDE為例，原本字串是遞增的 (以ASCII來看)
我們的最終目標是遞減的EDCBA (也就是最後一個 permutation)

下面列出前幾個 permutation :

ABCDE - ABCED - ABDCE - ABDEC - ABECD - ABEDC - ACBDE - ...

首先思考一下，我們寫一個字串的時候
第一個位置有5個選擇，第二個位置有4個，依此類推...
加上要按順序寫，所以第一個permutation產生的理由是
第一個位置可以選A~E，選擇最前面的A
第二個位置可以選B~E，同理
最後得到ABCDE

第二個permutation，由於第五個位置已經沒得選了
回到第四個位置，原本可以選D~E，現在選擇E，最後還是只能選D
所以得到ABCED

再者，第四個位置DE都選過了
所以往前到第三個位置，選擇C的下一個順位 D
D選完後，第四個位置可以選CE，選擇C，最後E
所以得到ABDCE

依此類推...

過程中
連續選過的位置會形成遞減的情況
往前找到沒有遞減的字元
取得該字元下一個順位後
後面的字元再形成他們自己的第一個 permutation
也就是字元由小到大排序的結果
最後就得到該次 permutation

[程式實作]
每次從後往前檢查兩兩相鄰字元
以ABEDC為例，找到BE為遞增，代表E以後都選完了

讓B換下一個順位(跟C換位置)      [ABEDC → ACEDB]

後面的字元們則由小到大排序即可 [ACEDB → ACBDE]

所以下一個為ACBDE

程式(Java):

	import java.util.*;
	public class Main {
	public static boolean nextPermutation(char[] num) {
	int len = num.length;
	int i, index = 0;
	char temp, value = '0';
	for (i = len - 1; i > 0; i--) {
	if (num[i - 1] < num[i]) {
	value = num[i - 1];
	index = i - 1;
	break;
	}
	}
	if (i == 0)
	return false;
	for (i = len - 1; i > index; i--) {
	if (num[i] > value) {
	temp = value;
	num[index] = num[i];
	num[i] = temp;
	break;
	}
	}
	Arrays.sort(num, index + 1, len);
	return true;
	}
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int n = Integer.valueOf(sc.nextLine());
	for (int i = 0; i < n; i++) {
	String s = sc.nextLine();
	char a[] = s.toCharArray();
	Arrays.sort(a);
	System.out.println(a);
	while (nextPermutation(a)) {
	System.out.println(a);
	}
	System.out.println();
	}
	}
	}

view raw UVa10098.java hosted with ❤ by GitHub