Combine similar character in string in C#

Question

I have a list of lists that contain integers (this list can be any length and can contain any number of integers:

{{1,2}, {3,4}, {2,4}, {9,10}, {9,12,13,14}}

What I want to do next is combine the lists where any integer matches any integer from any other list, in this case:

   result = {{1,2,3,4}, {9,10,12,13,14}}

I have tried many different approaches but am stuck for an elegant solution.

Answer 1

If you just mean "combine when there's an intersection", then maybe something like below, with output:

{1,2,3,4}
{9,10,12}

noting that it also passes the test in your edit, with output:

{1,2,3,4}
{9,10,12,13,14}

Code:

static class Program {
    static void Main()
    {
        var sets = new SetCombiner<int> {
            {1,2},{3,4},{2,4},{9,10},{9,12}
        };
        sets.Combine();
        foreach (var set in sets)
        {
            // edited for unity: original implementation
            // Console.WriteLine("{" +
            //    string.Join(",", set.OrderBy(x => x)) + "}");

            StringBuilder sb = new StringBuilder();
            foreach(int i in set.OrderBy(x => x)) {
                if(sb.Length != 0) sb.Append(',');
                sb.Append(i);
            }
            Console.WriteLine("{" + sb + "}");
        }
    }
}

class SetCombiner<T> : List<HashSet<T>>
{
    public void Add(params T[] values)
    {
        Add(new HashSet<T>(values));
    }
    public void Combine()
    {
        int priorCount;
        do
        {
            priorCount = this.Count;
            for (int i = Count - 1; i >= 0; i--)
            {
                if (i >= Count) continue; // watch we haven't removed
                int formed = i;
                for (int j = formed - 1; j >= 0; j--)
                {
                    if (this[formed].Any(this[j].Contains))
                    { // an intersection exists; merge and remove
                        this[j].UnionWith(this[formed]);
                        this.RemoveAt(formed);
                        formed = j;
                    }
                }
            }
        } while (priorCount != this.Count); // making progress
    }
}

Answer 2

Build custom comparer:

public class CusComparer : IComparer<int[]>
{
    public int Compare(int[] x, int[] y)
    {
        x = x.OrderBy(i => i).ToArray();
        y = y.OrderBy(i => i).ToArray();

        for (int i = 0; i < Math.Min(x.Length, y.Length); i++ )
        {
            if (x[i] < y[i]) return -1;
            if (x[i] > y[i]) return 1;
        }

         if (x.Length < y.Length) return -1;
        if (x.Length > y.Length) return 1;

        return 0;
    }
}

Then, order by custom comparer first:

List<int[]> input = new List<int[]>()
        {
            new[] { 3, 4 }, new[] { 1, 2 }, new[] { 2, 4 }, 
            new[] { 9, 10 }, new[] { 9, 12 }
        };

var orderedInput = input.OrderBy(x => x, new CusComparer()).ToList();

Use Intersect.Any() to check:

List<int[]> output = new List<int[]>();

int[] temp = orderedInput[0];

foreach (var arr in orderedInput.Skip(1))
{
    if (temp.Intersect(arr).Any())
        temp = temp.Union(arr).ToArray();

    else
    {
        output.Add(temp);
        temp = arr;
    }
}

output.Add(temp);