Linq Query Help Needed - Determining Exact Subsets

Question

Say I have the following string lists:

string[] list1 = { "one", "two", "three", "four"};
string[] list2 = { "one", "two", "three" };
string[] list3 = { "three", "two", "one" };

I need a query that allows me to compare list2 to list1 and return true if all the strings in list2 exist in list1, in the same order as list2.

So, such a query would return true if I compare list2 to list1 because all the strings in list2 are in list1, in the same order as list2.

The query would return false if I compare list3 to list1 because even though the strings in list3 exist in list1, they are not in the same order.

Is such a query possible?

Answer 1

If I understand what you're describing, this should do it:

list1.Intersect(list2).SequenceEquals(list2);

We first get the intersection of list1 and list2, which is { "one", "two", "three" }

Then use SequenceEquals to determine if that is the same as list1.

Answer 2

You basically have to iterate over both lists simultaneously. Try this:

public static bool IsOrderedSubsequenceOf<T>(
    this IEnumerable<T> smallerList,
    IEnumerable<T> largerList)
{
    IEqualityComparer<T> comparer = Comparer<T>.Default;

    using (var smallerIterator = smallerList.GetEnumerator())
    using (var largerIterator = largerList.GetEnumerator())
    {
        while (smallerIterator.MoveNext())
        {
            T currentTarget = smallerIterator.Current;
            bool found = false;
            while (largerIterator.MoveNext())
            {
                T candidate = largerIterator.Current;
                if (comparer.Equals(currentTarget, candidate))
                {
                    found = true;
                    break;
                }
            }
            if (!found)
            {
                // Exhausted iterator without finding target.
                return false;
            }
        }
    }
    // Found everything in the smaller sequence. Done.
    return true;
}

I haven't tested this or even compiled it, but I think it might work...

You'd call it with

if (list2.IsOrderedSubsequenceOf(list1))

If you can think of a better name (possibly putting the arguments the other way round) that would be good :)

Answer 3

How about this:

int pos = 0;
bool result = list1.Count(p => list2.Contains(p) && pos < list2.Length && list2[pos++] == p) == list2.Length;

This works in all cases I believe. Event for the following:

string[] list1 = { "one", "two", "four", "three" };
string[] list2 = { "one", "two", "three" };

The accepted answer will return false, even though all elements in list2 are in list1, on the same order.

EDIT: Will not work if list1 has repeated values contained in list2. As per comments below.