package main

func nextPermutationRune(runes []rune) {
	if len(runes) < 2 {
		return
	}
	var i int
	for i = len(runes) - 2; i >= 0; i-- {
		if runes[i] < runes[i+1] {
			break
		}
	}
	if i != -1 {
		var j int
		for j = i; j < len(runes)-1 && runes[j+1] > runes[i]; j++ {
		}
		runes[i], runes[j] = runes[j], runes[i]
	}
	for j, k := i+1, len(runes)-1; j < k; j, k = j+1, k-1 {
		runes[j], runes[k] = runes[k], runes[j]
	}
}

func getPermutationOld(n int, k int) string {
	res := make([]rune, 0)
	for i := 1; i <= n; i++ {
		res = append(res, rune('0'+i))
	}
	for i := 1; i < k; i++ {
		nextPermutationRune(res)
	}
	return string(res)
}

// (1 2 3 4) -> 4! permutaion
// 1 (2 3 4) -> 3! permutaion
// get 16th permutaion => 16 - 1 > 3! + 3!, so 3 (1 2 4)
// => 15 - 3! - 3! = 3 > 2!, so 3 2 (1 4)
// => 1, so 3 2 4 (1) => (append last candidate) 3 2 4 1
func getPermutation(n int, k int) string {
	res := make([]byte, 0)
	candidate := make([]byte, 0)
	for i := 0; i < n; i++ {
		candidate = append(candidate, byte('1'+i))
	}
	// k: the No. of permutation
	// k--: steps left to next permutation
	k--
	for i, base := n-1, fact(n-1); i > 0; i-- {
		idx := k / base
		res = append(res, candidate[idx])
		candidate = append(candidate[:idx], candidate[idx+1:]...)
		k -= idx * base
		base /= i
	}
	res = append(res, candidate...)
	return string(res)
}

func fact(x int) int {
	if x <= 1 {
		return 1
	}
	return x * fact(x-1)
}

/* func main() {
	fmt.Println(getPermutationOld(4, 16))
	fmt.Println(getPermutation(4, 16))
	fmt.Println(getPermutation(1, 16))
	fmt.Println(getPermutation(0, 16))
} */