分组为连续整数范围

Question

我检查了其他帖子，包括 使用 Linq 按变量整数范围分组，

但是我没有找到任何与我的问题类似的内容...我试图将整数序列分组为不连续的整数范围。例如，如果我有一组从 1 到 100 的连续整数，然后我的集合跳过 101，我想创建一个记录，该记录从记录 #1 和 #100 获取日期，其中记录 #1 的日期是开始日期，#100 是结束日期。

每个连续整数范围都会创建一个新记录，以添加到指示该范围开始和结束日期的记录列表中。如果范围仅包含一个整数值（例如，整数范围为 1-100、102 和 104-200），则单个整数范围将具有相同的开始和结束日期。

有什么建议吗？

Answer 1

您可以创建一个扩展方法来执行此操作：

static class EnumerableIntExtensions {
    public static IEnumerable<IEnumerable<T>> ToContiguousSequences<T>(
        this IEnumerable<T> sequence,
        Func<T, T> next
    ) {
        Contract.Requires(sequence != null);
        Contract.Requires(next != null);
        var e = sequence.GetEnumerator();
        if (!e.MoveNext()) {
            throw new InvalidOperationException("Sequence is empty.");
        }
        var currentList = new List<T> { e.Current };
        while (e.MoveNext()) {
            T current = e.Current;
            if (current.Equals(next(currentList.Last()))) {
                currentList.Add(current);
            }
            else {
                yield return currentList;
                currentList = new List<T> { current };
            }
        }
        yield return currentList;
    }
}

用法：

var sequence = Enumerable.Range(1, 100)
                         .Concat(new[] { 102 })
                         .Concat(Enumerable.Range(104, 97));
var sequences = sequence.ToContiguousSequences(n => n + 1);
foreach(var contiguousSequence in sequences) {
    Console.WriteLine(String.Join(", ", contiguousSequence.Select(n => n.ToString())));
}

输出：

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100
102
104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200

Answer 2

我不知道您是否能够使用提供的 LINQ 函数来执行此操作，但以下函数：

public static IEnumerable<IEnumerable<T>> GroupWhile<T>(this IEnumerable<T> values, Func<Int32, Boolean> predicate)
{
    var i = 0;
    var currentSet = new List<T>();
    while (i < values.Count())
    {
        if (predicate(i))
            currentSet.Add(values.Skip(i).First());
        else
        {
            yield return currentSet;
            currentSet = new List<T>(new[] {values.Skip(i).First()});
        }
        i++;
    }
    yield return currentSet;
}

使用如下：

var ints = new[] {1, 2, 4, 5, 7, 8};
var groups = ints.GroupWhile(i => i == 0 || ints[i - 1] == ints[i] - 1).ToList();

可能符合要求。

Answer 3

这是我创建的一个示例类，可能会有所帮助。它将整数序列转换为一组范围。该代码在 LINQPad 中运行。

void Main()
{
    ContiguousNumberLine line = new ContiguousNumberLine();

    List<Int64> testItems = new List<Int64>() { 1, 2, 4, 5, 7, 9, 11, 10, 3, 6, 8, 8 };
    foreach(Int64 item in testItems)
    {
        line.Add(item);
        line.numberLine.Dump(string.Format("After adding {0}", item));
    }

    line.Add(new List<Int64>() { 12, 14, 15, 16 });
    line.numberLine.Dump("After adding 12, 14, 15, 16");
    line.Add(new List<Int64>() { 17, 18, 19, 20 });
    line.numberLine.Dump("After adding 17, 18, 19, 20");

    foreach(var item in line.numberLine)
    {
        Console.WriteLine(string.Format("{0}\t{1}", item.Key, item.Value));
    }
}

// Define other methods and classes here
public class ContiguousNumberLine
{
    public SortedList<Int64, Int64> numberLine { get; private set; }

    public ContiguousNumberLine()
    {
        numberLine = new SortedList<Int64, Int64>();
    }

    public bool IsPresent(Int64 input)
    {
        if (numberLine.ContainsKey(input))
        {
            return true;
        }
        else
        {
            foreach(var numRange in numberLine)
            {
                if (numRange.Key > input)
                {
                    return false;
                }
                if (numRange.Value < input)
                {
                    continue;
                }
                if (numRange.Key <= input && input <= numRange.Value)
                {
                    return true;
                }
            }
            return false;
        }
    }

    public bool IsPresent(List<Int64> input)
    {
        if (IsContiguous(input))
        {
            return IsPresentRange(input.First(), input.Last());
        }
        else
        {
            foreach(Int64 item in input)
            {
                if (this.IsPresent(item))
                {
                    return true;
                }
            }
        }
        return false;
    }

    public bool IsPresentRange(Int64 first, Int64 last)
    {
        // naive implementation
        for(Int64 i = first; i <= last; i++)
        {
            if (this.IsPresent(i))
            {
                return true;
            }
        }
        return false;
    }

    public bool IsContiguous(List<Int64> input)
    {
        Int64? first = null;
        Int64? last = null;
        foreach(Int64 item in input)
        {
            if (first == null)
            {
                first = item;
                last = item;
                continue;
            }
            if (last.Value +1 == item)
            {
                last = item;
                continue;
            }
            else
            {
                return false;
            }
        }
        return true;
    }

    public bool Add(Int64 input)
    {
        if (IsPresent(input))
        {
            return false;
        }
        else
        {
            //numberLine.Add(input, input);
            // extend the last number of an existing range, then check if it bridges the gap to the next range
            KeyValuePair<Int64, Int64>? itemToRemove1 = null;
            KeyValuePair<Int64, Int64>? itemToRemove2 = null;
            KeyValuePair<Int64, Int64> itemToAdd = new KeyValuePair<Int64, Int64>(input, input) ;

            foreach(var numRange in numberLine)
            {
                if (numRange.Value + 1 == input)
                {
                    itemToRemove1 = numRange;
                    itemToAdd = new KeyValuePair<Int64, Int64>(numRange.Key, numRange.Value + 1);
                    continue;
                } else if (itemToRemove1 != null && numRange.Key -1 == input)
                {
                    itemToRemove2 = new KeyValuePair<Int64, Int64>(numRange.Key, numRange.Value);
                    KeyValuePair<Int64, Int64> newRange = new KeyValuePair<Int64, Int64>(itemToAdd.Key, numRange.Value);
                    itemToAdd = newRange;
                    break;
                } else if (numRange.Key - 1 == input)
                {
                    itemToRemove1 = numRange;
                    itemToAdd = new KeyValuePair<Int64, Int64>(input, numRange.Value);
                    break;
                } else if (numRange.Key > input)
                {
                    itemToAdd = new KeyValuePair<Int64, Int64>(input, input);
                    break;
                }
            }

            if (itemToRemove1 != null)
            {
                numberLine.Remove(itemToRemove1.Value.Key);
            }
            if (itemToRemove2 != null)
            {
                numberLine.Remove(itemToRemove2.Value.Key);
            }
            numberLine.Add(itemToAdd.Key, itemToAdd.Value);
            return true;
        }
    }

    public bool Add(List<Int64> input)
    {
        // check if we can use the optimized version
        if (IsContiguous(input))
        {
            return this.AddRange(input.First(), input.Last());
        }
        else
        {
            if(IsPresent(input))
            {
                return false;
            }
            foreach(Int64 item in input)
            {
                this.Add(item);
            }
            return true;
        }

    }

    public bool AddRange(Int64 first, Int64 last)
    {
        //throw new NotImplementedException();
        if(IsPresentRange(first, last))
        {
            return false;
        }
        // naive implementation below (TODO: write optimized version)
        for(Int64 i = first; i <= last; i++)
        {
            this.Add(i);
        }
        return true;
    }

}