参考というか大元です
HackerRankの問題を解いていたらつまづいた問題を解くために必要なアルゴリズム。以前どこかで見知った気もするが、覚えていないので、今回学んだことを整理しておく。
Next lexicographical permutation algorithmは、「辞書順での次の順列を求めるアルゴリズム」とでも訳したらいいのかな。lexicographical orderといったほうが一般的かもしれない。
問題
- 初めに文字列 S が与えらる。
- その文字列 S の文字の順序を入れ替えて S’ を作成する。
- このS'は辞書順で S よりも後に来るものとする。
- 複数パータンある場合は「辞書順で S よりも後」かつ「辞書順で最小のもの（次にくるもの）」を作成する。
具体的には、文字列S＝xyzikdcbaというが与えられたら、この文字を入れ替えて辞書順で次に来るS'＝xyzkabcdiを作成するアルゴリズムです。
辞書順について
私も詳しくないため言葉で説明するのは難しいので、実際にプログラムで見てみましょう。
scala> "abcd".permutations.toList.sorted
res1: List[String] = List(abcd, abdc, acbd, acdb, adbc, adcb, bacd,
badc, bcad, bcda, bdac, bdca, cabd, cadb,
cbad, cbda, cdab, cdba, dabc, dacb, dbac,
dbca, dcab, dcba)
これがa``b``c``dの４文字を組み合わせた時の辞書順になります。そして、例えばbadcが与えられたら、bcadを見つけ出すのが、このアルゴリズムです。
文字数が数文字ならばアルゴリズムには頼らず、ライブラリで順列を算出し、それをソートしてあげれば簡単に求まります。しかし文字数が、数十文字、数百文字となると順列のパターンもどんどん増えていくので、効率的に解くためにはアルゴリズムが必要になります。
解説
文字だとわかりづらいので解説では数字に置き換えて考える。コンピューター中では文字も数字なので同じことです。
S = 0 1 2 5 3 3 0
S' = 0 1 3 0 2 3 5
処理手順
Sの末尾から順に探索して、昇順が終わる位置を探す。
5の次に2が来るので昇順終了
↓ ← 末尾からみて昇順(0335)
0 1 2 5 3 3 0
昇順を終わらせた値[ 2 ] をpivotと呼び、末尾からみて昇順になっている部分をSuffix[ 5 3 3 0 ]とよびます
pivot
↓
0 1 2 |5 3 3 0|
| Suffix |
Suffixの中から、pivotよりも大きくて、Suffixの中で最小を値[ 3 ]を見つけ出す。
pivotより大きくて、suffixの中で最小
↓
0 1 2 |5 3 3 0|
↑ | Suffix |
pivot
そして、pivotと[ 3 ]を入れ替えます。[ 0 1 3 5 3 2 0]
swap
↓￣￣￣￣￣↓
0 1 3 |5 3 2 0|
| Suffix |
最後に、入れ替えたSuffix [ 5 3 2 0 ] の部分だけを昇順ソートしすると完成します。
0 1 3 |0 2 3 5|
| asc sort |
Scalaでプログラミング
javaやcなどは、上記したリンク先にあるので、そちらを参考にしてください。
object NextLexicographicalPermutation {
def main(args: Array[String]): Unit = {
val N = io.StdIn.readInt()
for (i <- 0 until N) {
val str: String = io.StdIn.readLine()
// Sの末尾から順に探索して、昇順が終わる位置を探す。
var i = str.length - 1
while (i > 0 && str(i - 1) >= str(i)) {
i -= 1
}
// 昇順が終わらせた値のindex
val pivotIndex = i - 1
if (pivotIndex < 0)
// pivotがなかった場合
println("nothing")
else {
// pivotと,Suffix内の値を入れ替える
var j = str.length - 1
while (str(j) <= str(pivotIndex)) {
j -= 1
}
val swapIndex = j
val strBuf = str.toBuffer
strBuf(pivotIndex) = str(swapIndex)
strBuf(swapIndex) = str(pivotIndex)
//入れ替えおwたSuffixをソートしたのち組み合わせて完成
val newStr = strBuf.mkString
val prefix = newStr.substring(0, pivotIndex + 1)
val suffix = newStr.substring(pivotIndex + 1)
val sortedSuffix = suffix.sorted
println(prefix + sortedSuffix)
}
}
}
}