代码之家 › 专栏 › 技术社区 › Tomislav Markovski

根据条件合并IEnumerable中的元素

collections algorithm .net c#

Tomislav Markovski · 技术社区 · 14 年前

我正在寻找一些快速有效的方法来合并数组中的项。这是我的设想。集合按排序。相邻的元素不一定相差1,即上一个To和下一个From之间可能有间隙,但它们从不重叠。

var list = new List<Range>();
list.Add(new Range() { From = 0, To = 1, Category = "AB" });
list.Add(new Range() { From = 2, To = 3, Category = "AB" });
list.Add(new Range() { From = 4, To = 5, Category = "AB" });
list.Add(new Range() { From = 6, To = 8, Category = "CD" });
list.Add(new Range() { From = 9, To = 11, Category = "AB" }); // 12 is missing, this is ok
list.Add(new Range() { From = 13, To = 15, Category = "AB" });

我希望上面的集合以这样的方式合并:前三个元素(这个数字可以变化,从至少2个元素到满足条件的任意多个元素)变成一个元素。无法合并具有不同类别的元素。

new Range() { From = 0, To = 5, Category = "AB" };

这样得到的集合总共有4个元素。

0 - 5    AB
6 - 8    CD
9 - 11   AB // no merging here, 12 is missing
13 - 15  AB

4 回复 | 直到 6 年前

James Curran 14 年前

这是一个通用的、可重用的解决方案,而不是一个临时的、特定的解决方案。 (根据评论更新)

IEnumerable<T> Merge<T>(this IEnumerable<T> coll, 
                      Func<T,T,bool> canBeMerged, Func<T,T,T>mergeItems)
{
    using(IEnumerator<T> iter = col.GetEnumerator())
    {
      if (iter.MoveNext())
      {
          T lhs = iter.Current;
          while(iter.MoveNext())
          {
              T rhs = iter.Current;
              if (canBeMerged(lhs, rhs)
                 lhs=mergeItems(lhs, rhs);
              else
              {
                 yield return lhs;
                 lhs= rhs;
              }
          }
          yield return lhs;
      }
    }
}

这些应该是你的Range类的一部分,所以可以这样命名:

list.Merge((l,r)=> l.IsFollowedBy(r), (l,r)=> l.CombineWith(r));

如果您没有这些方法,那么您必须像这样调用它:

list.Merge((l,r)=> l.Category==r.Category && l.To +1 == r.From,
           (l,r)=> new Range(){From = l.From, To=r.To, Category = l.Category});

Timwi 14 年前

var output = new List<Range>();
var currentFrom = list[0].From;
var currentTo = list[0].To;
var currentCategory = list[0].Category;
for (int i = 1; i < list.Count; i++)
{
    var item = list[i];
    if (item.Category == currentCategory && item.From == currentTo + 1)
        currentTo = item.To;
    else
    {
        output.Add(new Range { From = currentFrom, To = currentTo,
            Category = currentCategory });
        currentFrom = item.From;
        currentTo = item.To;
        currentCategory = item.Category;
    }
}
output.Add(new Range { From = currentFrom, To = currentTo,
    Category = currentCategory });

我想看看是否有一个解决方案更优化的性能。

编辑:我假设输入列表已排序。 如果不是这样,我建议先对它进行排序,而不是试图将其放入算法中。排序仅限于( n 日志 n ),但如果你想把它摆弄进去,你很容易得到( n

list.Sort((a, b) => a.From < b.From ? -1 : a.From > b.From ? 1 : 0);

作为旁白,

Thomas Levesque 14 年前

还有一个:

IEnumerable<Range> Merge(IEnumerable<Range> input)
{
    input = input.OrderBy(r => r.Category).ThenBy(r => r.From).ThenBy(r => r.To).ToArray();
    var ignored = new HashSet<Range>();
    foreach (Range r1 in input)
    {
        if (ignored.Contains(r1))
            continue;

        Range tmp = r1;
        foreach (Range r2 in input)
        {
            if (tmp == r2 || ignored.Contains(r2))
                continue;

            Range merged;
            if (TryMerge(tmp, r2, out merged))
            {
                tmp = merged;
                ignored.Add(r1);
                ignored.Add(r2);
            }
        }
        yield return tmp;
    }
}

bool TryMerge(Range r1, Range r2, out Range merged)
{
    merged = null;
    if (r1.Category != r2.Category)
        return false;
    if (r1.To + 1 < r2.From || r2.To + 1 < r1.From)
        return false;
    merged = new Range
    {
        From = Math.Min(r1.From, r2.From),
        To = Math.Max(r1.To, r2.To),
        Category = r1.Category
    };
    return true;
}

您可以直接使用它:

var mergedList = Merge(list);

但是如果你有很多项,那么效率会很低,因为复杂性是O(n)。但是,由于只能合并同一类别中的项,因此可以按类别对它们进行分组并合并每个组,然后展平结果:

var mergedList = list.GroupBy(r => r.Category)
                    .Select(g => Merge(g))
                    .SelectMany(g => g);

Ani 14 年前

假设列表已排序,并且范围不重叠,如您在问题中所述,这将在O(n)时间内运行:

var flattenedRanges = new List<Range>{new Range(list.First())};

foreach (var range in list.Skip(1))
{
    if (flattenedRanges.Last().To + 1 == range.From && flattenedRanges.Last().Category == range.Category)
        flattenedRanges.Last().To = range.To;
    else
        flattenedRanges.Add(new Range(range));
}

这是假设您有一个 Range

编辑: 这里有一个就地算法:

    for (int i = 1; i < list.Count(); i++)
    {
        if (list[i].From == list[i - 1].To+1  && list[i-1].Category == list[i].Category)
        {
            list[i - 1].To = list[i].To;
            list.RemoveAt(i--);
        }
    }

编辑: