1

私は関数型プログラミングにかなり慣れていないので、いくつかの練習問題を行っています。一意の自然の行列、たとえば5x5が与えられた場合に、関数を記述したいと思います。たとえば、3x3のように、より小さなサイズの一意の行列のコレクションを返します。ここで、行列はそのままである必要があります。つまり、元の値に隣接する値から作成されます。

01 02 03 04 05
06 07 08 09 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

単純。3つのグループで1つずつ横にスライドしてから下にスライドするだけで、次のようなものが得られます。

01 02 03 | 02 03 04 | 03 04 05 | 06 07 08
06 07 08 | 07 08 09 | 08 09 10 | 11 12 13
11 12 13 | 12 13 14 | 13 14 15 | 16 17 18

または、Scalaでは

List(List(1, 2, 3), List(6, 7, 8), List(11, 12, 13))
List(List(2, 3, 4), List(7, 8, 9), List(12, 13, 14))
List(List(3, 4, 5), List(8, 9, 10), List(13, 14, 15))
List(List(6, 7, 8), List(11, 12, 13), List(16, 17, 18))

などなど...

それで、私はScala（命令型から機能型に進化することができるので私の選択した言語）に挑戦し、ここ数年はJavaで過ごしました。

val array2D = "01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25".grouped(3).map(_.trim.toInt).grouped(5)
val sliced = array2D.map(row => row.sliding(3, 1).toList).sliding(3, 1).toList

これで、作業できるデータ構造ができましたが、機能的な方法がわかりません。確かに、私は各ピースをトラバースしsliced、作成し、var matrix = new ListBuffer[Seq[Int]]()それらのバッグを作成することができます。これで完了です。

Scalaを使用して、機能的で理想的にはポイントフリーのアプローチを見つけたいのですが、困惑しています。3などでzipする方法が必要です...ScalaDocsを検索しましたが、理解できないようです。

4

2 に答える 2

2

途中で着きました。実際、私はあなたがすでに行ったことをどのように行うかを理解するのに苦労していました。わかりやすくするために、コードを少し分割しました。また、を作成array2DしたListので、コードをより簡単に操作できました。:-)

val input = "01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25"
val intArray = (input split " " map (_.toInt) toList)
val array2D = (intArray grouped 5 toList)
val sliced = array2D.map(row => row.sliding(3, 1).toList).sliding(3, 1).toList

さて、あなたはたくさんのリストを持っています、それぞれは少しこのようです：

List(List(List( 1,  2,  3), List( 2,  3,  4), List( 3,  4,  5)), 
     List(List( 6,  7,  8), List( 7,  8,  9), List( 8,  9, 10)), 
     List(List(11, 12, 13), List(12, 13, 14), List(13, 14, 15)))

そして、あなたはそれらをこのようにしたい：

List(List(List(1, 2, 3), List(6, 7,  8), List(11, 12, 13)), 
     List(List(2, 3, 4), List(7, 8,  9), List(12, 13, 14)), 
     List(List(3, 4, 5), List(8, 9, 10), List(13, 14, 15)))

それはあなたにとって正しいと思いますか？3つのサブリストはそれぞれ、それ自体がマトリックスです。

List(List(1, 2, 3), List(6, 7,  8), List(11, 12, 13))

は

01 02 03
06 07 08
11 12 13

したがって、基本的には、それらを転置する必要があります。次のステップは次のとおりです。

val subMatrices = sliced map (_.transpose)

その種類はですList[List[List[Seq[Int]]]]。少し考えてみましょう...2D行列はシーケンスのシーケンスで表されるためList[Seq[Int]] 、マトリックスに対応します。まあ言ってみれば：

type Matrix = Seq[Seq[Int]]
val subMatrices: List[List[Matrix]] = sliced map (_.transpose)

ただし、行列のリストが1つ必要なので、次のように平坦化できます。

type Matrix = Seq[Seq[Int]]
val subMatrices: List[Matrix] = (sliced map (_.transpose) flatten)

しかし、残念ながら、mapプラスaflattenはflatMap：です。

type Matrix = Seq[Seq[Int]]
val subMatrices: List[Matrix] = sliced flatMap (_.transpose)

ここで、固有の部分行列が必要です。それは十分に単純です：それはセットです。

val uniqueSubMatrices = subMatrices.toSet

または、結果をシーケンスとして保持する場合は、

val uniqueSubMatrices = subMatrices.distinct

以上です。説明のための完全なコード：

type Matrix = Seq[Seq[Int]]
val input = "01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25"
val intArray = (input split " " map (_.toInt) toList)
val array2D: Matrix = (intArray grouped 5 toList)
val sliced: List[List[Matrix]] = (array2D map (row => row sliding 3 toList) sliding 3 toList)
val subMatrices: List[Matrix] = sliced flatMap (_.transpose)
val uniqueSubMatrices: Set[Matrix] = subMatrices.toSet

単一の式として書くこともできますが、関数に分割しない限り、読むのは恐ろしいことです。そして、フォワードパイプ（|>標準ライブラリではなく）を使用するか、これらの関数をそれらが作用する型に暗黙的に追加する必要があります。そうしないと、とにかく読むのが難しくなります。

于 2011-02-04T20:38:02.030 に答える
1

編集：さて、私はあなたが何を望んでいるかを最終的に理解したと思います。高性能な方法ではなく、機能する方法を紹介します。（これは一般的に変更可能なJavaのようなソリューションですが、その方法はすでに知っています。）

まず、2Dで適切に機能する独自のコレクションを使用して、これを実行する必要があります。多数の1Dコレクションを使用して2Dコレクションをエミュレートすると、不必要な混乱と複雑化につながります。しないでください。本当に。それは悪い考えです。

でも、とにかくやってみましょう。

val big = (1 to 25).grouped(5).map(_.toList).toList

これは、必要なマトリックス全体です。次、

val smaller = (for (r <- big.sliding(3)) yield r.toList).toList

必要な行のグループです。これで、1D操作にうまくマッピングされないことをしたいので、2Dデータ構造を使用する必要がありました。だが：

val small = smaller.map(xss =>
  Iterator.iterate(xss.map(_.sliding(3)))(identity).
    takeWhile(_.forall(_.hasNext)).
    map(_.map(_.next)).
    toList
).toList

これを注意深く引き離すと、一連のイテレータ（xss.map(_.sliding(3))）を作成し、同じイテレータを次々と保持し、少なくとも1つが空になると停止することで、すべてのイテレータをロックステップで反復していることがわかります。そしてそれらを次の値にマッピングします（これがあなたがそれらを前進させる方法です）。

行列ができたので、好きなように保存できます。個人的に、私はリストを平らにします：

val flattened = small.flatten

行列を並べた構造を作成しましたが、これもある程度の努力で行うことができます（1D操作から2D操作を作成するのは必ずしも簡単ではないため）。

val sidebyside = flattened.reduceRight((l,r) => (l,r).zipped.map(_ ::: _))

（これをO（n ^ 2）ではなくO（n）操作にするreduceRightに注意してください-長い累積リストの最後に結合することは悪い考えです-しかし、行列が多すぎるとスタックがオーバーフローする可能性があることにも注意してください）。

于 2011-02-04T14:48:38.423 に答える