Quick way to compare arrays with LINQ

Question

Is there a way to write short code in LINQ to check if one array is a subsequence of other and honor an order?

For example (pseudo code):

var masterList = new double[] {0,1,2,3,4};
var lst1 = new double[] {0,1,2,3};
var lst2 = new double[] {0,1,3,4};
var lst3 = new double[] {2,3,4};
var lst4 = new double[] {3,4};
var lst5 = new double[] {4,3};

bool isSubseq1 = lst1.Compare(masterList); // true
bool isSubseq2 = lst2.Compare(masterList); // false
bool isSubseq3 = lst3.Compare(masterList); // true
bool isSubseq4 = lst4.Compare(masterList); // true
bool isSubseq5 = lst5.Compare(masterList); // false

edit:

bool isSubseq = !lst5.Except(masterList).Any(); // returns true, but I want to return false

edit2: Example2:

var masterList = new double[] {0,1,2,3,4,4,4,5,6,6,8,8};
var lst1 = new double[] {0,1,2,3};
var lst2 = new double[] {0,3,4};
var lst3 = new double[] {4,4,4};
var lst4 = new double[] {6,6,8,8};
var lst5 = new double[] {5,4,4,4,3};
var lst6 = new double[] {9,9};

bool isSubseq1 = lst1.Compare(masterList); // true
bool isSubseq2 = lst2.Compare(masterList); // false
bool isSubseq3 = lst3.Compare(masterList); // true
bool isSubseq4 = lst4.Compare(masterList); // true
bool isSubseq5 = lst5.Compare(masterList); // false
bool isSubseq6 = lst6.Compare(masterList); // false

Yeah I could write my own method, but this is not I'm asking for. I will accept nested query.

**[101 LINQ Samples](https://code.msdn.microsoft.com/101-LINQ-Samples-3fb9811b)** — Ňɏssa Pøngjǣrdenlarp, Feb 06 '18 at 17:43
@Yuriy Faktorovich This is not a duplicate since the OP wants subset of same order. — Salah Akbari, Feb 06 '18 at 17:45
https://stackoverflow.com/questions/41538284/check-whether-array-is-in-another-array-but-in-order-and-elements-can-repeat — Yuriy Faktorovich, Feb 06 '18 at 17:46
@S.Akbari you're right, I almost want to reopen it, I've linked him to a question that includes ordering. — Yuriy Faktorovich, Feb 06 '18 at 17:47
Another [duplicate](https://stackoverflow.com/questions/26668718/) — Aleks Andreev, Feb 06 '18 at 17:48
@S.Akbari unfortunately I can't link to that question because it doesn't have an upvoted/selected answer. — Yuriy Faktorovich, Feb 06 '18 at 17:51
[This](https://stackoverflow.com/questions/332973/check-whether-an-array-is-a-subset-of-another) is not what I want. — H3ll0, Feb 06 '18 at 18:03
If you don't want the shown code to return true then you don't want to check for a subset, because that's exactly what it's doing. You're trying to check for a subsequence, apparently (a set being unordered, a sequence being ordered). — Servy, Feb 06 '18 at 18:11
@H3ll0 How do you imagine you will obtain the custom/specific logic you need _without_ writing your own method? You have two perfectly fine answers already. — maccettura, Feb 06 '18 at 19:01
@maccettura Well apparently they already knew how to do it even *before* getting an answer. They just didn't want to. — Servy, Feb 06 '18 at 19:03

score 1 · Answer 1 · answered Feb 06 '18 at 18:27

You can write your own method to do this. I made this one into an extension method:

public static class Extensions
{
    public static bool IsSubsequencetOf<T>(this T[] subset, T[] items)
    {
        if (subset.Length < 1)
            return true;
        if (items.Length < 1)
            return false;

        for (int itemsIndex = 0; itemsIndex <= items.Length - subset.Length; ++itemsIndex)
        {
            if (items[itemsIndex].Equals(subset[0])) // Found a potential start of the subset
            {
                bool isMatch = true;
                int itemsIndexInner = itemsIndex + 1;
                for (int subsetIndex = 1; itemsIndexInner < items.Length && subsetIndex < subset.Length; ++subsetIndex)
                {
                    if (!items[itemsIndexInner].Equals(subset[subsetIndex]))
                    {
                        isMatch = false;
                        break;
                    }

                    itemsIndexInner++;
                }

                if (isMatch)
                    return true;
            }
        }

        return false;
    }
}

You'd use it like so:

bool isSubsequence1 = lst1.IsSubsequencetOf(masterList);

score 1 · Answer 2 · answered Feb 06 '18 at 18:36

Here's another implementation of the same:

public static class LinqEx
{
    public static bool IsSubsequenceOf<T>(
        this IEnumerable<T> subSequence, 
        IEnumerable<T> sequence) where T : IEquatable<T>
    {
        var subSequenceIterator = subSequence.GetEnumerator();
        if (!subSequenceIterator.MoveNext()) return true;
        var started = false;
        foreach (var superitem in sequence)
        {
            if (superitem.Equals(subSequenceIterator.Current))
            {
                started = true;
                if (!subSequenceIterator.MoveNext()) return true;
            }
            else if (started)
            {
                return false;
            }
        }
        return false;
    }
}

...over your data:

bool isSubset1 = lst1.IsSubsequenceOf(masterList); // true
bool isSubset2 = lst2.IsSubsequenceOf(masterList); // false
bool isSubset3 = lst3.IsSubsequenceOf(masterList); // true
bool isSubset4 = lst4.IsSubsequenceOf(masterList); // true
bool isSubset5 = lst5.IsSubsequenceOf(masterList); // false

Yay.

H3ll0 · Accepted Answer · 2018-02-07T14:40:27.973

Based on Nacho's idea, this is my solution (not ideal, but I'll take it for now):

    [TestCase(new int[] { 0, 1, 2, 3 }, true)]
    [TestCase(new int[] { 0, 3, 4 }, false)]
    [TestCase(new int[] { 4, 4, 4 }, true)]
    [TestCase(new int[] { 6, 6, 8, 8 }, true)]
    [TestCase(new int[] { 5, 4, 4, 4, 3 }, false)]
    [TestCase(new int[] { 9, 9 }, false)]
    [TestCase(new int[] { 0, 2 }, false)]
    [TestCase(new int[] { }, false)] // bug: SkipWhile skips all master's items, so master[] { } == sub[] { } is true;
    public void MethodToTest(int[] sub, bool expected)
    {
        var master = new int[] { 0, 1, 2, 3, 4, 4, 4, 5, 6, 6, 8, 8 };

        var result = master.SkipWhile((x, i) => !master.Skip(i).Take(sub.Length).SequenceEqual(sub))
            .Take(sub.Length).SequenceEqual(sub);

        Assert.AreEqual(expected, result);
    }

Edit: Fixes empty array problem:

    var result = master.SkipWhile((x, i) => !master.Skip(i).Take(sub.Length).SequenceEqual(sub))
        .Take(sub.Length).DefaultIfEmpty().SequenceEqual(sub);

Quick way to compare arrays with LINQ

3 Answers3