２つのSeqのオブジェクトリストを特定の列で比較しマージしたい

Question

おはようございます。

下記のソースを見ていいただきたいのですが、aというリストの中のオブジェクトの"name"と
bというリストの中のオブジェクトの"pname"と比較し、一致したら、リストaの一致した後にデータを差し込みたいと考えております。

記述方法がわからないのが、リストbをみて頂きたいのですが、
Shime("C", "mm")をリストaに差し込んだ後、差し込まれたリストaを利用し、
リストbを比較し、Shime("斎藤", "C")をリストaに差し込まなければいけません。

単純に考えて、リストaとリストbを比較した際に、一致したら、リストaに差し込み、
リストbから削除するといったロジックにするのが良いかと思い、いざ実装をしているのですが、
思い通りの結果の記述ができませんでした。

難しく考えているのかもしれませんが、どうしてもわからないため、皆様のお力を
お借りできればと思っております。

  var a = Seq(Shime("A", "○"), Shime("B", "☓"))
  var b = Seq(Shime("伊藤", "A"), Shime("山田", "B"), Shime("C", "mm"), Shime("斎藤", "C"))

  case class Shime(name: String, pname: String)

  // 下記の結果になるようにしたい
  //
  // a =Seq(
  //   Shime("A", "○"),
  //   Shime("伊藤", "A"),
  //   Shime("B", "☓"),
  //   Shime("山田", "B"),
  //   Shime("C", "mm"),
  //   Shime("斎藤", "C")
  // )

大変、お手数をおかけしますが、ご教授よろしくお願いします。

---

ご指摘をいただきましたので、編集させて頂きます。

仕様があやふやで失礼いたしました。

ご質問いただきました、想定して頂いた内容で認識はあっていると思います。

今回、なぜ、このような投稿をしたかを、記載させて頂きます。

データベースからデータを取得し、指定の並び順、
更新日時でソートしたリストを表示しようと考えております。

単純にデータベース上に、並び順であったり、優先順のフィールドを設けておけば
解決するような内容ですが、データベースから取得したデータの更新頻度が多いため、
すべてのデータに並び順を持たせてしまうと、追加・削除毎に、採番し直す必要があった為、
他の方法を考えておりました。

考えた方法として、並び替えるデータがどのデータの後ろになるのか？を保持したテーブルを用意し、
プログラムで一覧を作成する際に、保持したテーブルを参照しデータの並び替えを行おうと考えております。

// データベースより取得したリスト
list = Seq("あ", "い", "う", "え", "お", "か")

// 並び替え対象リスト
order = Seq(Order("お","あ"), Order("え","お"))

case clase Order(
value: String, // 挿入する値
targetValue:String // ターゲットとなる値
)

// 結果
newlist = Seq("あ", "お", "え", "い", "う", "か")

処理方法としましては、

1.データを取得(A)
A ... リスト
B ... 並び替え対象リスト

2.リスト(A)を分割
分割条件: リスト(A)のデータが、並び替え対象リスト(B)の"挿入する値"と一致、かつ、ターゲットとなる値が、がリスト(A)に含まれている

A` ... 条件が一致せず残ったリスト
C ... 条件の一致したリスト

3.条件が一致せず残ったデータ(A)を、forなどで１件づつ処理を行い、並び替え対象のデータと一致した場合、Cのリストからデータを取得し、Aに挿入

と考えておりました。

プログラムを組んでうちに、3の段階時点で、"お"のつぎが"え"とならないのではないかと疑問に思い、今回、質問内容をやりたいことのみを記載し質問してしまいました。

難しく考え過ぎているのかもしれませんが、ご教授いただけると幸いです。

お手数をおかけしますが、よろしくお願い致します。

Answer 1

回答ではないのですが・・・

ご質問にはやりたいことの例しか述べられておらず「仕様」が述べられていません。いうまでもなく、仕様によってどのようなアルゴリズムを採るべきかは変化します。もし質問者さんが想定している仕様を明示せずその想定と違う前提を置いたアルゴリズムを回答者が回答してしまうと

「いえそういう仕様ではないのです」

といわないといけなくなりますね。ソフトウェアを設計する際に「利用者が正確な要件を言わない」といったことはよくあること(w;)と思いますが、そうした場合「正確な要件を確認する」ところから始めるべきであろうと思います。

例から想像すると以下のような規則であるように思えますが、このような前提をお考えなのかどうか確認したく思いました。

• 結果の末尾がShima(α,β)であるとき、a,bの残り要素にShima(?,α)はたかだか一つしかない
• 結果の末尾がShima(α,β)であるとき、a,bの残り要素にShima(?,α)がなければa,bの残り要素の先頭を次の要素とする
• 結果の最初の要素はa,bの残り要素の中の先頭要素とする

(最初の回答に書いた規則は曖昧だったので訂正しました。失礼しました。)

---

追記：補足された質問内容に従い考えてみました。結論からいうと最初のご質問にあるようなa, bのリストのうちaのみ用いる方法です。ちょっと分かりにくい論理にも見えるのでもっと明解な方法があるかも知れません。

object Reorder {
  case class Order(val next: String, val prev: String)

  def main(args: Array[String]): Unit = {
    // 並び替え対象リスト
    val list = Seq("あ", "い", "う", "え", "お", "か")
    // 順序制約リスト
    val order = Seq(Order("お","あ"), Order("え","お"))

    // 順序マップを作る(previous -> nextのペア)
    val orderMap = order.map(o ⇒ o.prev → o.next).toMap

    // 与えた引数から順序マップによって決まる固定的な順列を返す
    // マップ内に含まれない場合は単に引数を単一要素とする列を返す
    // (本件の場合"あ"を渡すとSeq("あ", "お", "え")が返ります。
    def makeOrderedSeq(s: String): Seq[String] = orderMap.get(s) match {
      case Some(next) ⇒ s +: makeOrderedSeq(next)
      case None ⇒ Seq(s)
    }

    // 順序マップ(のnext)に出現しないもののみの列へ要素を挿入
    val result = list
                .filter(s ⇒ order.forall(_.next != s))
                .flatMap(makeOrderedSeq(_))
    println(s"result = ${result}")
  }
}

上はあまり処理効率を気にしておらず順序制約のリストの長さが１０個やそこらの程度ならよいのですが、それ以上の長さだとmakeOrderedSeqが再帰になっているので危険かも知れません。
再帰を使わないと以下のような不格好なものになってしまいます・・・
Scala使いの方には「ひどいコード」と言われてしまいそうですが orz

def makeOrderedSeq(s: String): Seq[String] = orderMap.get(s) match {
  case Some(next) ⇒
    val b = mutable.Buffer(s)
    var n = next
    do {
      b += n
      n = orderMap.getOrElse(n, null)
    } while (n != null)
    b
  case None ⇒ Seq(s)
}

もっとよい回答があると思いますが自分の程度ではこのくらいの回答が関の山です。

Comments

[退会済みユーザー]

仕様があやふやで失礼いたしました。

ご質問いただきました、想定して頂いた内容で認識はあっていると思います。

今回、なぜ、このような投稿をしたかを、記載させて頂きます。

データベースからデータを取得し、指定の並び順、
更新日時でソートしたリストを表示しようと考えております。

単純にデータベース上に、並び順であったり、優先順のフィールドを設けておけば
解決するような内容ですが、データベースから取得したデータの更新頻度が多いため、
すべてのデータに並び順を持たせてしまうと、追加・削除毎に、採番し直す必要があった為、
他の方法を考えておりました。

考えた方法として、並び替えるデータがどのデータの後ろになるのか？を保持したテーブルを用意し、
プログラムで一覧を作成する際に、保持したテーブルを参照しデータの並び替えを行おうと考えております。

``` scala
// データベースより取得したリスト
list = Seq("あ", "い", "う", "え", "お", "か")

// 並び替え対象リスト
order = Seq(Order("お","あ"), Order("え","お"))

case clase Order(
value: String, // 挿入する値
targetValue:String // ターゲットとなる値
)

// 結果
newlist = Seq("あ", "お", "え", "い", "う", "か")
```

処理方法としましては、

1.データを取得(A)
　A ... リスト
B ... 並び替え対象リスト

2.リスト(A)を分割
　分割条件: リスト(A)のデータが、並び替え対象リスト(B)の"挿入する値"と一致、かつ、ターゲットとなる値が、がリスト(A)に含まれている

　A` ... 条件が一致せず残ったリスト　
　C ... 条件の一致したリスト

3.条件が一致せず残ったデータ(A`)を、forなどで１件づつ処理を行い、並び替え対象のデータと一致した場合、Cのリストからデータを取得し、A`に挿入

と考えておりました。

プログラムを組んでうちに、3の段階時点で、"お"のつぎが"え"とならないのではないかと疑問に思い、今回、質問内容をやりたいことのみを記載し質問してしまいました。

難しく考え過ぎているのかもしれませんが、ご教授いただけると幸いです。

お手数をおかけしますが、よろしくお願い致します。

[KSwordOfHaste]

並び替え対象リストがAの全てを網羅してはいないが、最も優先して先に並べるべきものを表しているということですね。ちなみに上の内容はコメント欄に書くより質問文を編集して書いた方が適切だと思います。

[KSwordOfHaste]

さらにいえば、B(=Order(x,y))の条件として
1) xやyはAに含まれないこともある
2) Aの要素にはBの中のxやyに含まれないこともある(BはAの全てを網羅してはいない)
3) Bはどのxも他のxとは重複しない。yも同様。
かどうかがポイントになると思います・・・
---
失礼しました。上1～3は無視してください。コメントにあるC(条件の一致したリスト）はしかるべき順番に並んでいるという仮定でよいでしょうか。並んでないと本質問の処理をしても元の要件に合致しないので。
---
すみません、結局「しかるべき順番に並ぶかどうか」に依存しない論理としました。

[退会済みユーザー]

早速のご回答ありがとうございます。
本文に質問を加筆させて頂きました。

ご指摘頂きましたCは、然るべき順番に並んでいる想定でございます。

[退会済みユーザー]

ご回答ありがとうございます。

サンプルを頂き、自分なりに書いてみました。
再帰の使い方が、わかりやすく、再帰処理を利用して、コーディングすることにしました。

Scalaに対して勉強不足なので、ご教授頂き、とても勉強になりました。

ありがとうございました。

[KSwordOfHaste]

再帰アルゴリズムだと多分orderの件数がそのまま再帰呼び出しのネストの深さになりますのでスタックオーバーフローが起きることのないよう注意しておいた方がよいと思います。