Reputation: 13
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
Reputation: 726987
Use Disjoint-Set Forest data structure. The data structure supports three operations:
MakeSet(item
) - creates a new set with a single itemFind(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
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
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