7

開始インデックスと終了インデックスを持つ行を表すペアのリストがあります。型は (Int,Int) で、2 つの整数のタプルです。

ここで、たとえば、互いに接触している線を結合したいと考えています。

List( (1,5),(6,10),(12,20) ) は List( (1,10), (12,20) ) に変換する必要があります。行 (1,5) が行 (6,10) に接しているためです。 ）。接触している線のみが 1 つの線に結合されます。

私の最初の考えは、リストで foldleft を使用することでした。問題は、foldleft が 2 つの要素を 1 つに変換する必要があり、最終的には 1 つの (Int,Int) 出力だけになってしまうことです。

2番目に考えたのは、私がプログラムした再帰的なソリューションですが、これは最善または最も単純なアイデアではないようです。2 つの要素を取り、時には 1 つまたは 2 つの要素を出力するという考えは、foldleft のように、多くの場合に適用されるべきもののように思えます。

この問題を解決するための一般的な方法、パターン、またはライブラリはありますか?

1 本の線は 1 次元平面上にあり、x、y 点ではありません。(Int,Int) は、1 次元平面上の始点と終点です。

触れることの定義を明確にする。リスト内のどの行も重複していません。これは前提条件です。つまり、(1, 3) と (2, 4) は重複しているためリストに存在できません。

(1,3)、(4,5) は重複しないため、リストに存在する可能性があります。

(1,3)、(4,5) は、3 と 4 の間の距離がちょうど 1 であるため、接触します。

質問 ((1, 5), (6, 10), (6, 12), (13, 15)) で与えられたリストの場合、(6, 10), (6, 12 ) 重なります。

参考までに、これは私がこの質問をここに書く前の私の作業コードです。結果を構築して結果を返す再帰関数の構築に関する知識を使用していました。

  private def joinAtoB(a: LineLike, b: LineLike): LineLike = {
    newFunction(a.start, b.end)
  }

  private def joinTouchingLines(a: LineLike, b: LineLike): Option[LineLike] = {
    if ((a.end + 1) == b.start)
      Some(joinAtoB(a, b))
    else
      None
  }

  @tailrec
  def joinLinesRec(list: List[LineLike], result: List[LineLike] = List[LineLike]())
                     :List[LineLike] = {
    list match {
      case Nil => result
      case item :: Nil => item :: result

      case first :: second :: rest => {
        val joined = joinTouchingLines(first, second)
        val prepend = joined match {
          case None => List(first, second)
          case Some(joinedItem) => List(joinedItem)
        }
        joinLinesRec(rest, prepend ::: result)
      }
    }
  }
4

2 に答える 2

5

隣接する要素が接触する場合を除いて、cons ( ) を模倣するバイナリ関数foldRightの代わりに使用できます。foldLeft::

def combine(x: (Int, Int), lst: List[(Int, Int)]) = (x, lst) match {
  case (_, Nil) => List(x)
  case ((a, b), (c, d) :: rest) => if (c == b+1)
                                     (a, d) :: rest
                                   else
                                     (a, b) :: lst
}
于 2012-12-29T13:20:38.200 に答える
2

これを foldLeft で実行するのは簡単ですが、オーバーラップまたはタッチしているときに支配する部分を取り除くと、さらに簡単になります。

def touching(fp: (Int, Int), sp: (Int, Int)) = 
  if (fp._2 >= sp._1) sys.error("Overlap " + fp + " and " + sp) 
  else if (fp._2 == sp._1 - 1) true 
  else false

次に、いつ追加するか、最後のペアをいつ拡張するかを決定できます。

list.foldLeft(List[(Int,Int)]()){
  (l, p) => 
    if (l.isEmpty || !touching(l.head, p)) p :: l
    else (l.head._1, p._2) :: l.tail
}.reverse
于 2012-12-29T13:16:27.823 に答える