以更长的顺序查找子序列

Question

我需要在其他大序列中找到一个序列,例如,{1,3,2,3}存在于{1,3,2,3,4,3}和中{5,1,3,2,3}.有没有办法快速与IEnumerable其他东西一起做？

Answer 1

此方法将在父序列中找到可以通过Equals()以下方式进行比较的任何类型的子序列:

public static bool ContainsSubequence<T>(this IEnumerable<T> parent, IEnumerable<T> target)
{
    bool foundOneMatch = false;
    using (IEnumerator<T> parentEnum = parent.GetEnumerator())
    {
        using (IEnumerator<T> targetEnum = target.GetEnumerator())
        {
            // Get the first target instance; empty sequences are trivially contained
            if (!targetEnum.MoveNext())
                return true;

            while (parentEnum.MoveNext())
            {
                if (targetEnum.Current.Equals(parentEnum.Current))
                {
                    // Match, so move the target enum forward
                    foundOneMatch = true;
                    if (!targetEnum.MoveNext())
                    {
                        // We went through the entire target, so we have a match
                        return true;
                    }
                }
                else if (foundOneMatch)
                {
                    return false;
                }
            }

            return false;
        }
    }
}

你可以像这样使用它:

bool match = new[] {1, 2, 3}.ContainsSubsequence(new[] {1, 2}); // match == true
match = new[] {1, 2, 3}.ContainsSubsequence(new[] {1, 3}); // match == false

请注意,它假定目标序列没有null元素.

更新:感谢大家的赞成,但上面的代码实际上有一个错误!如果找到了部分匹配,但是之后没有变成完全匹配,则该过程结束,而不是重置(当应用于类似的东西时,这显然是不相关的{1, 2, 1, 2, 3}.ContainsSubsequence({1, 2, 3})).

上面的代码非常适用于子序列的更常见定义(即不需要连续),但是为了处理重置(大多数IEnumerators不支持),需要预先枚举目标序列.这导致以下代码:

public static bool ContainsSubequence<T>(this IEnumerable<T> parent, IEnumerable<T> target)
{
    bool foundOneMatch = false;
    var enumeratedTarget = target.ToList();
    int enumPos = 0;

    using (IEnumerator<T> parentEnum = parent.GetEnumerator())
    {
        while (parentEnum.MoveNext())
        {
            if (enumeratedTarget[enumPos].Equals(parentEnum.Current))
            {
                // Match, so move the target enum forward
                foundOneMatch = true;
                if (enumPos == enumeratedTarget.Count - 1)
                {
                    // We went through the entire target, so we have a match
                    return true;
                }

                enumPos++;
            }
            else if (foundOneMatch)
            {
                foundOneMatch = false;
                enumPos = 0;

                if (enumeratedTarget[enumPos].Equals(parentEnum.Current))
                {
                    foundOneMatch = true;
                    enumPos++;
                }
            }
        }

        return false;
    }
}

此代码没有任何错误,但不适用于大型(或无限)序列.

Answer 2

与@dlev相似，但这也可以处理 {1,1,1,2}.ContainsSubsequence({1,1,2})

public static bool ContainsSubsequence<T>(this IEnumerable<T> parent, IEnumerable<T> target)
{
    var pattern = target.ToArray();
    var source = new LinkedList<T>();
    foreach (var element in parent) 
    {
        source.AddLast(element);
        if(source.Count == pattern.Length)
        {
            if(source.SequenceEqual(pattern))
                return true;
            source.RemoveFirst();
        }
    }
    return false;
}

Answer 3

您可以尝试这样的事情来开始。将此列表转换为字符串后，您可以使用子字符串查找序列：

if (String.Join(",", numericList.ConvertAll<string>(x => x.ToString()).ToArray())
{
    //get sequence
}