nextPermutation
キーワード
概要
配列を受け取って、全ての順列を列挙する。
入力は昇順にソートされている必要がある。
破壊的であることに注意。
compは比較関数で、a < bのとき負の数、a == bのとき 0、a > bのとき正の数を返す。
intの場合は func(a, b int) int {return b-a} として定義する。
計算量
提出コード
// comp is a function that returns a negative number if a < b, 0 if a == b, and a positive number if a > b
func nextPermutation[T any](arr []T, comp func(a, b T) int) bool {
n := len(arr)
i := n - 1
for i > 0 && comp(arr[i], arr[i-1]) >= 0 {
i--
}
if i <= 0 {
return false
}
j := n - 1
for comp(arr[j], arr[i-1]) >= 0 {
j--
}
arr[i-1], arr[j] = arr[j], arr[i-1]
j = n - 1
for i < j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
return true
}