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)、削除されたセットとソース セット (4) の結合である新しい結果セットを追加します (3)。

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