CODEWITHSUNDEEP
c#algorithm
Novice
Novice

Reputation: 913

Converting sets of integers into ranges using C#

What's the most idiomatic way to convert a set of integers into a set of ranges?

E.g. given the set {0, 1, 2, 3, 4, 7, 8, 9, 11} I want to get { {0,4}, {7,9}, {11,11} } using C#

This question is already answered in C++ @ Solution in C++

Upvotes: 7

Views: 879

Answers (3)

Alastair Maw
Alastair Maw

Reputation: 5482

This isn't very efficient, but it is idiomatic:

var nums = new HashSet<int>{0, 1, 2, 3, 4, 7, 8, 9, 11};
IEnumerable<Tuple<int, int>> ranges = Enumerable.Zip(
    nums.Where(n => !nums.Contains(n - 1)),
    nums.Where(n => !nums.Contains(n + 1)),
    Tuple.Create);

More efficient, assuming it's sorted:

public IEnumerable<Tuple<int, int>> GetContiguousRanges(IEnumerable<int> nums)
{
    int start = nums.First();
    int last = start - 1;
    foreach (int i in nums)
    {
        if (i != last + 1)
        {
            yield return Tuple.Create(start, last);
            start = i;
        }
        last = i;
    }
    yield return Tuple.Create(start, last);
}

Upvotes: 11

Ivan
Ivan

Reputation: 1256

Try K-means clustering to get the ranges. You'll need to specify how many different ranges you want.

Upvotes: 0

luqui
luqui

Reputation: 60463

This should be a pretty straightforward transliteration from the post you mentioned. Make sure you put this code in a class somewhere, C# code has to be in a class. I'm assuming you are not very familiar with C#, so I'll do enough to show the similarities and differences, and hopefully you can handle the rest.

struct Range
{
    public Range (int start, int end) { this.start = start; this.end = end; }
    public int start;
    public int end;
}

public static void SetToRanges(Dictionary<int,bool> indices, List<Range> ranges) 
{
    Range r = new Range(int.MinValue, int.MaxValue);
    foreach (int i in indices.Keys)
    {
        // translate rest of code here
    }
    ranges.Add(r);
    return ranges;
}

For a more idiomatic soluiton, I would return an IEnumerable<Range>, so the "list" can be built and iterated simultaneously:

public static IEnumerable<Range> SetToRanges(Dictionary<int, bool> indices)
{
     // instead of "ranges.Add(r)", use "yield return r".
     // This returns multiple values in order from the function, that can
     // be iterated with "foreach (Range i in SetToRanges(foo))"
}

Upvotes: 3

Related Questions