重複は残す差集合の取り方

Question

List<int> list1 { 1, 2, 3, 1, 3 }
//このリストに存在しない要素を抜き出す
List<int> list2 { 3, 4, 5 }
list1 - list2の結果の求め方について質問です。

1,2,1,3のリストとなる方法を教えていただけないでしょうか
list1.Except(list2)
とした場合、重複が排除されてしまい、
1,2
となってしまいます。
foreachで回すのも一致したらlist.Remove というのも試したりしていますが、同じような結果になってしまって、分からなくなってしまいます。

list2 - list1の場合は4,5のリストとなってほしいです。

List<int> list1 { 4, 3}
List<int> list2 { 3, 4, 5 }
この場合
list1 - list2の場合、空のリストとなり、
list2 - list1の場合、5 のリスト

となって欲しいです。

Comments

[Zuishin]

1, 2, 1, 3 ではなく、1, 2, 1 ではありませんか？

[koz555]

いえ、1.2.3.1が希望になります。
同じ値だとしても、比較先にある数の分だけ除いた形が欲しいです。
一度だけ差を取る感じです。

[Zuishin]

質問とまた数字が変わっています。

[koz555]

すみません、質問通り、1,2,1,3です。

[Zuishin]

list1 から取り除くのは Where でできます。
マッチした際に list2 からその値を取り除けばいいでしょう。

[episteme]

双方あらかじめソートしておくことを許すなら、端から順に比較すれば楽に見つかるんだけども...

[koz555]

事前にソートしておいても問題ありません。
結果も並び順は問いません。
ソートやWhereで考えていますが、
端から順とはどのようにするのでしょうか？forのindexを最大から比較、という事でしょうか

[episteme]

回答しました

Answer 1

foreachで回すのも一致したらlist.Remove というのも試したりしていますが、同じような結果になってしまって、分からなくなってしまいます。

Removeは最初に出現したものいっこだけ削除のはずですが、逆にどういうコードを書いているんでしょうか？
List<T>.Remove(T) メソッド (System.Collections.Generic) | Microsoft Docs

{
    // list2を順に回しlist1に最初に出現したものを削除
    var list1 = new List<int> { 1, 2, 3, 1, 3 };
    var list2 = new List<int> { 3, 4, 5 };
    foreach (var i in list2)
    {
        list1.Remove(i);
    }
    Console.WriteLine(string.Join(", ", list1)); // 1, 2, 1, 3
}
{
    var list1 = new List<int> { 1, 2, 3, 1, 3 };
    var list2 = new List<int> { 3, 4, 5 };
    foreach (var i in list1)
    {
        list2.Remove(i);
    }
    Console.WriteLine(string.Join(", ", list2)); // 4, 5
}

{
    // list1の中でlist2から削除できなかったものだけ抽出
    var list1 = new List<int> { 1, 2, 3, 1, 3 };
    var list2 = new List<int> { 3, 4, 5 };
    var list = list1.Where(x => !list2.Remove(x)).ToList();
    Console.WriteLine(string.Join(", ", list)); // 1, 2, 1, 3
}
{
    var list1 = new List<int> { 1, 2, 3, 1, 3 };
    var list2 = new List<int> { 3, 4, 5 };
    var list = list2.Where(x => !list1.Remove(x)).ToList();
    Console.WriteLine(string.Join(", ", list)); // 4, 5
}

LINQタグもあるのでLINQ版もやりましたが、副作用があるのは個人的には嫌ですね^^;

Comments

[koz555]

出来ました・・・助かりました・・・Linq版の方が短いので使いたくなりましたが副作用は良くないと確かによく聞くのでforeach版で行きます。
無条件にRemoveを流せば良かったんですね。。。
ここを色々と条件をつけて一致した時のみRemoveしようとして余計な混乱し、どう書けばいいのか分からなくなっていました。

Answer 2

双方あらかじめソートしておくことを許すなら、端から順に比較すれば楽に見つかるんだけども...

やってみた:

using System.Collections.Generic;

public class foo {
    public static void Main() {
        List<int> list1 = new List<int> { 1, 2, 3, 1, 3 };
        List<int> list2 = new List<int> { 3, 4, 5 };

        list1.Sort();
        list2.Sort();

        int n1 = 0;
        int n2 = 0;

        while ( n1 < list1.Count && n2 < list2.Count ) {
            if ( list1[n1] < list2[n2] ) {
                Console.WriteLine(list1[n1]);
                ++n1;
            } else {
                if ( list1[n1] >= list2[n2] ) {
                    ++n1;
                }
                ++n2;
            }
        }
        while ( n1 < list1.Count ) {
            Console.WriteLine( list1[n1] );
            ++n1;
        }
    }
}

Comments

[koz555]

ありがとうございます！
よく思いつきますね・・・すごいです。
ただ、Remove()をよく理解出来ていませんでした。申し訳ありませんがRemoveの方で目的の動作が確認出来ましたので、今回はそちらをベストアンサーとしました。