Обнаружение последовательности не менее 3 последовательных чисел из заданного списка - PullRequest
Новая
       39

Обнаружение последовательности не менее 3 последовательных чисел из заданного списка

22 голосов
/ 02 октября 2010

У меня есть список номеров, например 21,4,7,9,12,22,17,8,2,20,23

Я хочу иметь возможность выбирать последовательности последовательных чисел (минимум 3 элемента в длину), поэтому из приведенного выше примера это будет 7,8,9 и 20,21,22,23.

Я поиграл с несколькими уродливыми растягивающимися функциями, но мне интересно, есть ли изящный LINQ-иш способ сделать это.

Есть предложения?

UPDATE:

Большое спасибо за все ответы, очень ценится. Сейчас я играю со всеми, чтобы понять, какие из них лучше всего интегрируются в наш проект.

Ответы [ 12 ]

0 голосов
/ 02 октября 2010

Linq - это не решение для всех, иногда вам удобнее с простым циклом. Вот решение с небольшим количеством Linq, чтобы упорядочить исходные последовательности и отфильтровать результаты 

void Main()
{
    var numbers = new[] { 21,4,7,9,12,22,17,8,2,20,23 };
    var sequences =
        GetSequences(numbers, (prev, curr) => curr == prev + 1);
        .Where(s => s.Count() >= 3);
    sequences.Dump();
}

public static IEnumerable<IEnumerable<T>> GetSequences<T>(
    IEnumerable<T> source,
    Func<T, T, bool> areConsecutive)
{
    bool first = true;
    T prev = default(T);
    List<T> seq = new List<T>();
    foreach (var i in source.OrderBy(i => i))
    {
        if (!first && !areConsecutive(prev, i))
        {
            yield return seq.ToArray();
            seq.Clear();
        }
        first = false;
        seq.Add(i);
        prev = i;
    }
    if (seq.Any())
        yield return seq.ToArray();
}
0 голосов
/ 02 октября 2010

Вот решение, которое я выбрал в F #, должно быть довольно легко перевести это в запрос C # LINQ, так как сворачивание в значительной степени эквивалентно агрегирующему оператору LINQ. 

#light

let nums = [21;4;7;9;12;22;17;8;2;20;23]

let scanFunc (mainSeqLength, mainCounter, lastNum:int, subSequenceCounter:int, subSequence:'a list, foundSequences:'a list list) (num:'a) =
        (mainSeqLength, mainCounter + 1,
         num,
         (if num <> lastNum + 1 then 1 else subSequenceCounter+1),
         (if num <> lastNum + 1 then [num] else subSequence@[num]),
         if subSequenceCounter >= 3 then
            if mainSeqLength = mainCounter+1
                then foundSequences @ [subSequence@[num]]
            elif num <> lastNum + 1
                then foundSequences @ [subSequence]
            else foundSequences
         else foundSequences)

let subSequences = nums |> Seq.sort |> Seq.fold scanFunc (nums |> Seq.length, 0, 0, 0, [], []) |> fun (_,_,_,_,_,results) -> results
Страница:
...