CODEWITHSUNDEEP
c#.net
user2804123
user2804123

Reputation: 13

Merging arrays with common element

I want to merge arrays with common element. I have list of arrays like this:

List<int[]> arrList = new List<int[]>
{
    new int[] { 1, 2 },
    new int[] { 3, 4, 5 },
    new int[] { 2, 7 },
    new int[] { 8, 9 },
    new int[] { 10, 11, 12 },
    new int[] { 3, 9, 13 }
};

and I would like to merge these arrays like this:

List<int[]> arrList2 = new List<int[]>
{
    new int[] { 1, 2, 7 },
    new int[] { 10, 11, 12 },
    new int[] { 3, 4, 5, 8, 9, 13 } //order of elements doesn't matter
};

How to do it?

Upvotes: 1

Views: 252

Answers (3)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727027

Use Disjoint-Set Forest data structure. The data structure supports three operations:

  • MakeSet(item) - creates a new set with a single item
  • Find(item) - Given an item, look up a set.
  • Union(item1, item2) - Given two items, connects together the sets to which they belong.

You can go through each array, and call Union on its first element and each element that you find after it. Once you are done with all arrays in the list, you will be able to retrieve the individual sets by going through all the numbers again, and calling Find(item) on them. Numbers the Find on which produce the same set should be put into the same array.

This approach finishes the merge in O(α(n)) amortized (α grows very slowly, so for all practical purposes it can be considered a small constant).

Upvotes: 1

MarcinJuraszek
MarcinJuraszek

Reputation: 125660

I'm pretty sure it is not the best and the fastest solution, but works.

static List<List<int>> Merge(List<List<int>> source)
{
    var merged = 0;
    do
    {
        merged = 0;
        var results = new List<List<int>>();
        foreach (var l in source)
        {
            var i = results.FirstOrDefault(x => x.Intersect(l).Any());
            if (i != null)
            {
                i.AddRange(l);
                merged++;
            }
            else
            {
                results.Add(l.ToList());
            }
        }

        source = results.Select(x => x.Distinct().ToList()).ToList();
    }
    while (merged > 0);

    return source;
}

I've used List<List<int>> instead of List<int[]> to get AddRange method available.

Usage:

var results = Merge(arrList.Select(x => x.ToList()).ToList());

// to get List<int[]> instead of List<List<int>>
var array = results.Select(x => x.ToArray()).ToList();

Upvotes: 1

Piotr Kołaczkowski
Piotr Kołaczkowski

Reputation: 2629

Let each number be a vertex in the labelled graph. For each array connect vertices pointed by the numbers in the given array. E.g. given array (1, 5, 3) create two edges (1, 5) and (5, 3). Then find all the connected components in the graph (see: http://en.wikipedia.org/wiki/Connected_component_(graph_theory))

Upvotes: 3

Related Questions