読者です 読者をやめる 読者になる 読者になる

2016年8月7日

日記

プログラミングで順列をクラスとして抜き出したとき、順序付けを定義しようとしたんだが(Scala では、Ordered Java では Comparable を実装する)、ちょっと問題が。 最初、順列の2行記法での下段の数字の並びを使って辞書順序で定義しようとしたんだが、この順序で全順列を生成して Seq にすると(たとえば Permutation#allPermutations(degree: Int): Seq[Permutation] みたいなメソッドで生成)、昇順に並んだ Seq (たとえば Seq(1, 2, 3, 4))に順次生成した順列(置換)を適用して得られる列は、辞書順序にならない。

trait Permutation{
  def apply[E](seq: Seq[E]): Seq[E]  // seq に置換を適用
}

object Permutation{
  def allPermutations(degree: Int): Seq[Permutation]
}

val seq = Seq(1, 2, 3, 4)

Permutation.allPermutations(4).map(_(seq))  // 返される Seq[Seq[Int]] は辞書順ではない

さてどうしたもんか。

ツイート (ツイート数 65)