-2

Is there any elegant way in c# to check whether a List<T> contains a sub-List<T> similar to string.Contains(string)?

Let's say e.g. I want to test for example whether List A is contained in List B

List<int> A = new List<int>{ 1, 2, 3, 4, 3, 4, 5 };
List<int> B = new List<int>{ 3, 4, 5 };

important is that all elements have to match in exactly that order.

I know I could possibly do something like

bool Contains(List<Sampletype> source, List<Sampletype> sample)
{
    // sample has to be smaller or equal length
    if (sample.Count > source.Count) return false;

    // doesn't even contain first element
    if (!source.Contains(sample[0])) return false;

    // get possible starts
    // see https://stackoverflow.com/a/10443540/7111561
    int[] possibleStartIndexes = source.Select((b, i) => b == sample[0] ? i : -1).Where(i => i != -1).ToArray();

    foreach (int possibleStartIndex in possibleStartIndexes)
    {
        // start is too late -> can't match
        if (possibleStartIndex + sample.Count - 1 > source.Count - 1) return false;

        for (int index = possibleStartIndex; index < possibleStartIndex + sample.Count; index++)
        {
            // if one element does not match the whole sample doesn't match
            if (source[index] != sample[index]) return false;
        }

        // if this is reached all elements of the sample matched
        Debug.Log("Match found starting at index " + possibleStartIndex);
        return true;
    }

    return false;
}

But I hope there is a better way to do so.

derHugo
  • 83,094
  • 9
  • 75
  • 115
  • 3
    So, this is effectively a "substring" search. Sounds like, rather than reinventing the wheel, you should attempt to implement [K-M-P algorithm](https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm). – spender Feb 13 '19 at 18:28
  • You could use Enumerable.Intersect then count the result ? - https://learn.microsoft.com/en-us/dotnet/api/system.linq.enumerable.intersect?view=netframework-4.7.2 – Sam Feb 13 '19 at 18:28
  • we could build a wrapper around these classes and give them unique IDs. Class AList{List my_345List{get;set; } – aspxsushil Feb 13 '19 at 18:33
  • @spender while the duplicate solves what I'm doing in a better and beautiful way as far as I understand it you are right and implementing that algorithm would be more efficient since it avoids the looping over all elements, thanks for the input, I'll try that as well! – derHugo Feb 14 '19 at 05:22
  • @aspxsushil sorry I don't see at which point this would help? – derHugo Feb 14 '19 at 05:24

2 Answers2

6

Here's a oneliner:

var result = A.Select(a => $"{a}").Aggregate((c, n) => $"{c};{n}").Contains(B.Select(b => $"{b}").Aggregate((c, n) => $"{c};{n}"));

It basically creates a string from each list, and checks whether the A string contains the B string. This way you won't just get a method like string.Contains, you actually get to use just that.

EDIT Added separator to the string aggregations, as {1, 2, 3} would result in the same string as {1, 23}

EDIT 2 Re-adding my first approach which identifies if list B is present in list A, perhaps scattered, but still ordered:

var result = B.Intersect(A).SequenceEqual(B)
Kristoffer Lerbæk Pedersen
  • 607
  • 4
  • 12
  • 2
    You don't need `ToList()`, `SequenceEqual()` works on `IEnumerable` which is returned by `Intersect` – adjan Feb 13 '19 at 18:35
  • An `Intersect` of { 1, 2, 3, 4, 6, 3, 5 } and { 3, 4, 5 } would produce { 3, 4, 5 }. This would not produce the correct evaluation. – Eliasar Feb 13 '19 at 18:42
  • @Adrian: My bad, I'll remove ToList(). – Kristoffer Lerbæk Pedersen Feb 13 '19 at 18:45
  • Furthemore, I found that I intersected in the wrong order, fixing that too – Kristoffer Lerbæk Pedersen Feb 13 '19 at 18:46
  • @Eliasar, ah, sorry, I missed that they were not allowed to be scattered. – Kristoffer Lerbæk Pedersen Feb 13 '19 at 18:48
  • @KristofferLerbækPedersen according to the example of { 1, 2, 3, 4, 6, 3, 5 }, there is no sequence of { 3, 4, 5}. `Intersect` would produce that result, giving a false positive – Eliasar Feb 13 '19 at 18:49
  • Edited it with a oneliner that should do the trick. Not as pretty, though. – Kristoffer Lerbæk Pedersen Feb 13 '19 at 19:06
  • If you create an extension method, you can name it something like `ContainsSequence` – Eliasar Feb 13 '19 at 19:29
  • @KristofferLerbækPedersen thanks for your efforts! The duplicate link solves this in a better way. **However** though Eliasar is right and the example didn't show it I might be also interested in finding scattered patterns (I actually didn't exclude the possibility - just said the order is important) so I'ld like to upvoted your answer for the previous version using `B.Intersect(A).SequenceEqual(B);` – derHugo Feb 14 '19 at 05:16
  • Actually you did exclude the scattered pattern in your question, as you asked for functionality similar to `string.Contains(string)`, which was the part I missed.I agree that the duplicate link is more elegant, and it's what I'd go with as well, I just thought I'd leave my alternative approach here. I'll re-add my first answer and clarify that it's for a scattered pattern, and I'm glad you found use for it. – Kristoffer Lerbæk Pedersen Feb 14 '19 at 09:10
  • @KristofferLerbækPedersen hehe yeah actually I didn't think about the scattered version until you poeple mentioned it here .. than I thought like "hmm actually very usefull as well" ^^ – derHugo Feb 18 '19 at 14:59
0

Essentially you want to slide over A and check each element of that window with the B. The last part is actually SequenceEqual and I do recommend to use it but this is just an alternative to explain the point:

bool equal = Enumerable.Range(0, A.Count() - B.Count() + 1)
    .Select(i => A.Skip(i).Take(B.Count))
    .Any(w => w.Select((item, i) => item.Equals(B[i])).All(item => item));
Johnny
  • 8,939
  • 2
  • 28
  • 33