Алгоритм поиска непрерывных дней в неделе

Пользователь может выбрать любое количество дней недели из списка. Алгоритм должен найти самую длинную непрерывную группу выбранных дней. День начала может быть после дня окончания, если группа занимает две недели. Если это делает его проще, только группа, по крайней мере, 3 дня должны быть обнаружены. При пересечении границы недели это составляет максимум одну группу. (Не может быть двух групп по 3 дня в течение недели, которые не связаны.)

Например, если пользователь выбирает понедельник, вторник, Среда и суббота из списка, дисплей должен быть что-то вроде "понедельник-среда и суббота".

Другой пример: Ср, Пт, Сб, вс, пн - > "ср, пт-Пн".

Существует ли эффективный алгоритм для этого, предпочтительно в C# или аналогичном языке? Моя c# hackwork теперь занимает больше страницы (ВКЛ. несколько комментариев) и все еще не закончен.

2 3
algorithm weekday dayofweek

2 ответа:

Используйте Этот ответ , слегка измененный:

Используйте модифицированную версию dtb ' s GroupAdjacentBy, которая принимает minCount в качестве параметра: 

public static IEnumerable<IEnumerable<T>> GroupAdjacentBy<T>(
    this IEnumerable<T> source, Func<T, T, bool> predicate, int minCount)
{
    using (var e = source.GetEnumerator())
    {
        if (e.MoveNext())
        {
            var list = new List<T> { e.Current };
            var pred = e.Current;
            while (e.MoveNext())
            {
                // if adjacent, add to list
                if (predicate(pred, e.Current))
                {
                    list.Add(e.Current);
                }
                else
                {
                    // otherwise return previous elements:
                    // if less than minCount elements,
                    // return each element separately
                    if (list.Count < minCount)
                    {
                        foreach (var i in list)
                            yield return new List<T> { i };
                    }
                    else
                    {
                        // otherwise return entire group
                        yield return list;
                    }

                    // create next group
                    list = new List<T> { e.Current };
                }
                pred = e.Current;
            }
            yield return list;
        }
    }
}

И измените критерии для GroupAdjacentBy, чтобы также группировать по недельным переходам: 

// week starts with Monday, so this should
// represent: Wed, Fri, Sat, Sun, Mon
int[] array = new int[] { 1, 2, 4, 5, 6, 0 };

Func<int, int, bool> adjacentCriteria = (x, y) => (x+1==y) || (x==6 && y==0);

string result = string.Join(", ", array
    .GroupAdjacentBy(adjacentCriteria, 3)
    .Select(g => new int[] { g.First(), g.Last() }.Distinct())
    .Select(g => string.Join("-", g)));

Console.WriteLine(result); // output: 1, 2, 4-0
2

Я закончил свою версию этого. Он немного длиннее, чем другой, но с другой стороны, он также обрабатывает текстовое представление и выполняет именно эту задачу. Как насчет этого?

using System;
using System.Text;

namespace WeekMathTest
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] weekDayNames = new string[] {
                "Mon",
                "Tue",
                "Wed",
                "Thu",
                "Fri",
                "Sat",
                "Sun"
            };

            WeekDays weekDays = WeekDays.Monday | WeekDays.Tuesday | WeekDays.Thursday | WeekDays.Saturday | WeekDays.Sunday;

            Console.WriteLine(WeekDayGroup(weekDays, weekDayNames));
        }

        static string WeekDayGroup(WeekDays weekDays, string[] weekDayNames)
        {
            int groupStart = 0, groupEnd = 0, groupLength = 0;
            int maxGroupStart = 0, maxGroupEnd = 0, maxGroupLength = 0;

            // Iterate all days in a repeated range
            // (Sat/Sun doesn't need to be repeated or it would be in the first group)
            for (int day = 1; day <= 7 + 5; day++)
            {
                // Is this day set?
                int bitValue = 1 << ((day - 1) % 7);
                bool daySet = ((int) weekDays & bitValue) != 0;
                if (daySet)
                {
                    if (groupStart == 0)
                    {
                        // First day set, remember it as group start
                        groupStart = day;
                        groupEnd = day;
                        groupLength = 1;
                    }
                    else
                    {
                        // Group has already been started, set new end
                        groupEnd = day;
                        groupLength = groupEnd - groupStart + 1;
                        if (groupLength == 7)
                        {
                            // Seen every day of the week, stop here
                            break;
                        }
                    }
                }
                else
                {
                    if (groupLength >= 3 && groupLength > maxGroupLength)
                    {
                        // Group was long enough and longer than the last one, save it
                        maxGroupStart = groupStart;
                        maxGroupEnd = groupEnd;
                        maxGroupLength = groupLength;
                    }
                    // Reset operation variables
                    groupStart = 0;
                    groupEnd = 0;
                    groupLength = 0;
                }
            }
            // Final check
            if (groupLength >= 3 && groupLength > maxGroupLength)
            {
                // Group was long enough and longer than the last one, save it
                maxGroupStart = groupStart;
                maxGroupEnd = groupEnd;
                maxGroupLength = groupLength;
            }

            // Clear all group days from the original value
            for (int day = maxGroupStart; day <= maxGroupEnd; day++)
            {
                int bitValue = 1 << ((day - 1) % 7);
                weekDays = (WeekDays) ((int) weekDays & ~bitValue);
            }

            // Generate output string
            StringBuilder sb = new StringBuilder();
            for (int day = 1; day <= 7; day++)
            {
                int bitValue = 1 << ((day - 1) % 7);
                bool daySet = ((int) weekDays & bitValue) != 0;
                if (daySet)
                {
                    if (sb.Length > 0) sb.Append(", ");
                    sb.Append(weekDayNames[day - 1]);
                }
                else if (day == maxGroupStart)
                {
                    if (sb.Length > 0) sb.Append(", ");
                    sb.Append(weekDayNames[day - 1]);
                    sb.Append("-");
                    sb.Append(weekDayNames[(maxGroupEnd - 1) % 7]);
                }
            }
            return sb.ToString();
        }

        [Flags]
        enum WeekDays
        {
            Monday = 1,
            Tuesday = 2,
            Wednesday = 4,
            Thursday = 8,
            Friday = 16,
            Saturday = 32,
            Sunday = 64
        }
    }
}
0