未分類

Permutation Sequence

Backtracking, Go, LeetCode, Math

Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. “123”
  2. “132”
  3. “213”
  4. “231”
  5. “312”
  6. “321”

Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.

提示 解題應用
Backtracking 規律觀查
Math 排序組合

Default:

1
2
3
func getPermutation(n int, k int) string {
}

解答思路:

一開始本來想用遞回來列出所有結果，但只是要其中的第k個而且又有規律存在，所以應該可以直接算出第k個的組合是什麼，以上述的範例來說，仔細觀查的話會發現1開頭的組合有2個，2開頭的組合也有2個以此類推，也就是說長度為3的組合有3*2*1=6種，取了第一個值後剩下的組合就剩2*1=2種，到這邊都只是排序組合的概念，如果k值減去開頭為1的組合(2種)後，k值還大於0表示開頭不為1仍要向後不斷尋找(-2)，一直到k值小於等於0才可以確定k是落在開頭為x的組合之間，並藉由k值的正負數變化開始找開頭為x的第y個，最後就是不斷重覆上述方式一直到找出長度為3(n)的結果為止。

程式碼解說:

一開始先將n值初始化為1~n的字串元素陣列，以方便我們在找出開頭為x值時能從陣列移除來避免重覆取值，同時利用一變數暫存n!的值用以後續一邊找出所有長度的組合有多少個，接著才正式開始尋找第k個的組合，利用一迴圈從第1個值的位置開始尋找第k個的組合，先將之前的暫存值除去n以曉得取了一個值後剩下各別的組合有幾種，接下來就是不斷的將k值與暫存值相減到k小於等於0才可以確定k是落在開頭為x的組合之間，不過雖然是說不斷與暫存值相減，但其實直接將k值與暫存值相除就可以曉得落在第x組(例:開頭為1的當作1組)，而如果相除後餘數大於0表是是在下一組，x的位置就要+1，至於k值就是剛才所剩下的餘數代表開頭為x的第y個，如果餘數為0(非大於0)則表示是在開頭為x的最後一個組合，也就是暫存值的長度(取了一個值後剩下各別的組合有幾種)，此時的k要記得存入暫存值，知道落在第x組後就直接將x-1作為index值從陣列取出值放入結果字串中，並將x位置的值能從陣列移除(重組陣列)來避免後續重覆取值，最後直到n的長度歸0(每找出一個值便將n-1)表示已經出結果才做回傳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var pos int
var result string
tmp := 1
set := make([]string, n)
for i := 1; i <= n; i++ {
	set[i-1] = string(i + 48)
	tmp *= i
}
for n > 0 {
	tmp /= n
	pos = k / tmp
	if k%tmp > 0 {
		pos++
		k = k % tmp
	} else {
		k = tmp
	}
	result += set[pos-1]
	set = append(set[:pos-1], set[pos:]...)
	n--
}
return result

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func getPermutation(n int, k int) string {
	var pos int
	var result string
	tmp := 1
	set := make([]string, n)
	for i := 1; i <= n; i++ {
		set[i-1] = string(i + 48)
		tmp *= i
	}
	for n > 0 {
		tmp /= n
		pos = k / tmp
		if k%tmp > 0 {
			pos++
			k = k % tmp
		} else {
			k = tmp
		}
		result += set[pos-1]
		set = append(set[:pos-1], set[pos:]...)
		n--
	}
	return result
}

總結:

給一n代表一陣列元素1~n，將元素依序做排列組合，要求出第k個的結果，其做法就是利用排列組合的概念從1開始有(n-1)!種組合，並不斷將k值與(n-1)!相減直到k小於等於0才可以確定k是落在開頭為x的組合之間，並藉由k值的正負數變化開始找開頭為x的第y個，最後就是不斷重覆上述方式一直到找出長度為n的結果為止。

分享到