Finding consecutive subsequences of a given sequence

בעיה שיצא לי להתקל בה מספר פעמים היא הבעיה הבאה: נתונה לנו סדרה של איברים כך שלכל איבר יש אינדקס, ולצורך העניין האינדקסים ממוינים בסדר עולה (ממש).
אנחנו מעוניינים לאגד לקבוצות איברים הנמצאים בסדרה עם אינדקסים עוקבים.

בבעיה הזאת אפשר להתקל במספר מקומות:

• קריאת קובץ, סינון כל השורות שעונות על קריטריון מסוים (למשל, כל השורות שכתובות באנגלית), ויצירת קובץ חדש בו יש פסקה המכילה כל רצף כנ”ל של שורות:

string[] lines = File.ReadAllLines(fileLocation);

var relevantLines =
    lines.Select((x, i) => new
                               {
                                   Line = x,
                                   Index = i
                               })
         .Where(x => IsRelevant(x.Line));

// Group elements that their indexes form a consecutive subsequence

• מציאת מספרים בטקסט (בלי Regex)
• איגוד ימי חופש רצופים של עובד

הבעיה היא בעיה שיחסית קל לפתור ע"י קוד אימפרטיבי:
נגדיר מבנה שמייצג תת-סדרה רצופה:

public class ConsecutiveSubsequence
{
    public int StartIndex { get; set; }
    public int EndIndex { get; set; }
}

וניצור מתודה שמוצאת את כל התת-סדרות הרצופות הנ"ל:

public static IEnumerable<ConsecutiveSubsequence> FindConsecutiveSubsequences<T>
    (IEnumerable<T> sequence,
     Func<T, int> indexSelector)
{
    List<ConsecutiveSubsequence> result = new List<ConsecutiveSubsequence>();

    ConsecutiveSubsequence currentSequence = null;

    foreach (T current in sequence)
    {
        int currentIndex = indexSelector(current);

        if ((currentSequence == null) ||
            (currentSequence.EndIndex + 1 != currentIndex))
        {
            currentSequence = new ConsecutiveSubsequence();
            currentSequence.StartIndex = currentIndex;
            result.Add(currentSequence);
        }

        currentSequence.EndIndex = currentIndex;
    }

    return result;
}

נוכל להשתמש במתודה כך:

IEnumerable<ConsecutiveSubsequence> subsequences =
    FindConsecutiveSubsequences(relevantLines,
                               x => x.Index);

שימו לב שכרגע המתודה מחזירה רק את האינדקסים שבהם מתחילה ונגמרת כל תת-סדרה רצופה. אפשר לשנות את המתודה או לכתוב מתודה אחרת כך שיחזרו התת סדרות עצמן.

כל זה טוב ויפה, אבל מעניין האם ניתן לפתור את הבעיה בעזרת תכנות פונקציונאלי?

התשובה שהיא שכן, להלן הפתרון:

public static IEnumerable<ConsecutiveSubsequence> FindConsecutiveSubsequences<T>
    (IEnumerable<T> sequence,
     Func<T, int> indexSelector)
{
    List<int?> indexes = 
        sequence.Select(x => (int?)indexSelector(x)).ToList();

    IEnumerable<int?> nullAndIndexes =
        new int?[] {null}.Concat(indexes);

    IEnumerable<int?> indexesAndNull =
        indexes.Concat(new int?[] {null});


    var zipped =
        nullAndIndexes.Zip(indexesAndNull,
                           (x, y) => new
                                         {
                                             Current = x,
                                             Next = y
                                         });

    var disconsecutive =
        zipped.Where((x, index) => x.Next != x.Current + 1)
              .ToList();

    var disconsecutiveShifted = disconsecutive.Skip(1);

    IEnumerable<ConsecutiveSubsequence> result =
        disconsecutive.Zip
            (disconsecutiveShifted,
             (x, y) => new ConsecutiveSubsequence()
                           {
                               StartIndex = x.Next.Value,
                               EndIndex = y.Current.Value,
                           });

    return result;
}

בעצם מה שאנחנו עושים זה יוצרים מהאינדקסים שהתקבלו במתודה, זוגות המייצגים אינדקסים עוקבים בסדרה, זאת באמצעות האופרטור Zip המקבץ לנו שתי סדרות לסדרה אחת. (הערה: אנחנו שמים null לפני האינדקס הראשון וnull בתור האינדקס האחרון, כדי שנוכל להתחשב גם באינדקסים בקצוות)

כעת אנחנו מחפשים איפה נשבר הרצף, כלומר את הזוגות שבהם האיבר הבא בסדרה, אינו שווה למספר העוקב של האיבר הנוכחי בסדרה. בעזרת מקומות אלה אנחנו יכולים לגלות איפה מתחילה ואיפה נגמרת תת סדרה רצופה!

איך? בזוג המייצג קפיצה, האינדקס הקטן הוא האינדקס בו נגמר הרצף הקודם, האינדקס הגדול הוא האינדקס בו מתחיל הרצף החדש. מצורף שרטוט להמחשה (התאים הצהובים הם הזוגות שמייצגים קפיצות)

לכן כדי למצוא את התת-סדרות הרצופות, מספיק לנו להסתכל על האיבר Next של איבר בזוג ועל האיבר Current של הזוג העוקב. זאת אנחנו עושים שוב אמצעות המתודה Zip, אבל הפעם גם באמצעות האופרטור Skip המדלג לנו על האיבר הראשון בסדרה, כדי שנקבל זוגות של איברים עוקבים.

שבוע מאונדקס לטובה,
אלעד