c# - 在C#中组合字符串中的相似字符

Question

我有一个包含整数的列表列表（此列表可以是任意长度，并且可以包含任意数量的整数：

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

我接下来要做的是组合任何整数与任何其他列表中的任何整数匹配的列表，在这种情况下：

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

我尝试了许多不同的方法，但被困在一个优雅的解决方案中。

Answer 1

如果您的意思是“在有交叉点时合并”，那么可能类似于下面的输出：

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

请注意，它还在您的编辑中通过了测试，并带有输出：

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

代码：

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

构建自定义比较器：

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;
    }
}

然后，首先通过自定义比较器订购：

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();

用于Intersect.Any()检查：

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);

Answer 3

这是一个使用 LINQ 的简单、灵活的解决方案Aggregate：

void Main()
{
    var ints = new []{new []{1,2},new []{3,4},new []{2,4},new []{9,10},new []{9,12}};
    var grouped = ints.Aggregate(new List<HashSet<int>>(), Step);

    foreach(var bucket in grouped)
        Console.WriteLine(String.Join(",", bucket.OrderBy(b => b)));
}

static List<HashSet<T>> Step<T>(List<HashSet<T>> all, IEnumerable<T> current)
{
    var bucket = new HashSet<T>();

    foreach (var c in current)
        bucket.Add(c);

    foreach (var i in all.Where(b => b.Overlaps(bucket)).ToArray())
    {
        bucket.UnionWith(i);
        all.Remove(i);
    }
    all.Add(bucket);

    return all; 
}

Answer 4

我们维护一个结果集列表 (1)。对于每个源集，删除与其相交的结果集 (2)，并添加一个新的结果集 (3)，它是已删除集和源集 (4) 的并集：

class Program {

    static IEnumerable<IEnumerable<T>> CombineSets<T>(
        IEnumerable<IEnumerable<T>> sets,
        IEqualityComparer<T> eq
    ) {

        var result_sets = new LinkedList<HashSet<T>>();         // 1

        foreach (var set in sets) {
            var result_set = new HashSet<T>(eq);                // 3
            foreach (var element in set) {
                result_set.Add(element);                        // 4
                var node = result_sets.First;
                while (node != null) {
                    var next = node.Next;
                    if (node.Value.Contains(element)) {         // 2
                        result_set.UnionWith(node.Value);       // 4
                        result_sets.Remove(node);               // 2
                    }
                    node = next;
                }
            }
            result_sets.AddLast(result_set);                    // 3
        }

        return result_sets;

    }

    static IEnumerable<IEnumerable<T>> CombineSets<T>(
        IEnumerable<IEnumerable<T>> src
    ) {
        return CombineSets(src, EqualityComparer<T>.Default);
    }

    static void Main(string[] args) {

        var sets = new[] {
            new[] { 1, 2 }, 
            new[] { 3, 4 }, 
            new[] { 2, 4 }, 
            new[] { 9, 10 }, 
            new[] { 9, 12, 13, 14 }
        };

        foreach (var result in CombineSets(sets))
            Console.WriteLine(
                "{{{0}}}",
                string.Join(",", result.OrderBy(x => x))
            );

    }

}

这打印：

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

Answer 5

好的，我 LINQed 了！希望这是你想要的......疯狂的一个;）

void Main()
{
    var matches = new List<List<ComparissonItem>> { /*Your Items*/ };

    var overall =
        from match in matches
        let matchesOne =
            (from searchItem in matches
             where searchItem.Any(item => match.Any(val => val.Matches(item) && !val.Equals(item)))
             select searchItem)
        where matchesOne.Any()
        select
            matchesOne.Union(new List<List<ComparissonItem>> { match })
            .SelectMany(item => item);

    var result = overall.Select(item => item.ToHashSet());
}

static class Extensions
{

    public static HashSet<T> ToHashSet<T>(this IEnumerable<T> enumerable)
    {
        return new HashSet<T>(enumerable);
    }
}

class ComparissonItem
{
    public int Value { get; set; }

    public bool Matches(ComparissonItem item)
    {
        /* Your matching logic*/
    }

    public override bool Equals(object obj)
    {
        var other = obj as ComparissonItem;
        return other == null ? false : this.Value == other.Value;
    }

    public override int GetHashCode()
    {
        return this.Value.GetHashCode();
    }
}