-4

整数のリストがあるとします

List<int> l1 = new List<int> { 1, 4, 1};

このリスト内に別のリストが何回あるかを調べたい.たとえば

List<int> l2 = new List<int> { 1 , 1 } occours 1 time. 

List<int> l3 = new List<int> { 4, 1 } occours 1 time.

List<int> l4 = new List<int> {1} occours 2 times.

List<int> l5 = new List<int> {6,4,1} occours 0 time.

List<int> l5 = new List<int> {4,1,1} occours 1 time.

前もって感謝します

4

2 に答える 2

2

ここでの私の考えは、元のリスト内の各要素をその出現頻度にマップする辞書を作成することです。次に、値の 1 つがゼロになるまで、サブリスト内の 1 に対応する各項目を繰り返し減少させます。ゼロになった時点で、完全な反復回数を返します。

public static int CountSubsets<T>(this IList<T> list, IList<T> subList)
{
    var grouped = list.GroupBy(t => t).ToDictionary(t => t.Key, t => t.Count());
    int count = 0;
    while (RemoveSubset(grouped, subList))
        count++;
    return count;
}

private static bool RemoveSubset<T>(Dictionary<T, int> dict, IList<T> subList)
{
    foreach (T item in subList)
    {
        if (dict.ContainsKey(item) && dict[item] > 0)
            dict[item]--;
        else
            return false;
    }

    return true;
}

必ずしも最も効率的または最も洗練されたソリューションではありませんが、うまくいくはずです。

編集：これは空想ですが、おそらくより遅い方法です。私はこれにかなり満足しています：

public static int CountSubsets2<T>(this IList<T> list, IList<T> subList)
{
    var main = list.GroupBy(t => t).ToDictionary(t => t.Key, t => t.Count());
    var sub = subList.GroupBy(t => t).ToDictionary(t => t.Key, t => t.Count());
    return sub.Select(t => main.ContainsKey(t.Key) ? main[t.Key] / t.Value : 0).Min();
}
于 2013-09-08T16:14:34.953 に答える