Zbieranie grupy zbiorów 3-elementowych,

Dana jest lista liczb całkowitych:

000, 001, 002,
000, 002, 005,
002, 007, 005,
005, 007, 011,
005, 011, 014,
011, 016, 014,
018, 005, 014,
018, 014, 023,
023, 014, 026,
027, 028, 029,
027, 029, 000,
029, 034, 000,
036, 027, 000,
036, 000, 041,
041, 000, 044,
014, 046, 047,
014, 047, 027,
047, 052, 027,
026, 014, 027,
026, 027, 059,
059, 027, 036,
044, 000, 005,
044, 005, 068,
068, 005, 018,
072, 073, 074,
073, 076, 074,
073, 079, 076,
081, 082, 083,
081, 083, 086,
086, 083, 089,
086, 089, 092,
092, 089, 073,
092, 073, 098,
089, 100, 073,
102, 103, 104,
102, 104, 107,
108, 109, 110,
110, 109, 113,
110, 113, 102,
082, 118, 083,
082, 121, 104,
121, 107, 104,
082, 104, 118,
129, 082, 131,
131, 082, 134,
134, 082, 137,
098, 073, 140,
140, 073, 072,
140, 072, 146,
146, 072, 109,
146, 109, 108,
153, 002, 001,
153, 007, 002,
153, 011, 007,
153, 016, 011,
153, 047, 046,
153, 052, 047,
153, 029, 028,
153, 034, 029,
177, 072, 074,
177, 074, 076,
177, 076, 079,
177, 100, 089,
177, 089, 083,
177, 083, 118,
177, 118, 104,
177, 104, 103,
177, 113, 109,
177, 109, 072,
207, 018, 023,
207, 023, 026,
207, 026, 059,
207, 059, 036,
207, 036, 041,
207, 041, 044,
207, 044, 068,
207, 068, 018,
231, 081, 086,
231, 086, 092,
231, 092, 098,
231, 098, 140,
231, 140, 146,
231, 146, 108,
231, 108, 110,
231, 110, 102,
231, 102, 107,
231, 107, 121,
231, 129, 131,
231, 131, 134,
231, 134, 137,

Każde kolejne 3 liczby stanowią jeden byt. Nie można ich rozdzielać.
Chcę podzielić trójki liczb na grupy.
W każdej grupie trójki mają wspólną cechę - co najmniej jedna liczba ma taką samą wartość w dwóch trójkach.
Można by rzec, że trójki liczb tworzą grafy połączeń.

Czyli np. 044, 000, 005(1), 207, 041, 044(2), 005, 011, 014(3), 014, 046, 047(4) powinny należeć do tej samej grupy.
Dlatego, że (1) i (2) zawierają 044, (1) i (3) zawierają 005, (3) i (4) zawierają 014.

Poleci ktoś jakiś algorytm na to, żeby listę trójek podzielić na grupy według kryteriów?
Jakby co, język docelowy: C#.

Można to zrobić za pomocą jakiejś wariacji disjoint sets. Koncepcyjnie, jak sam zauważyłeś, to jest graf. Problem w języku grafów można wyrazić jako poszukiwanie spójnych składowych.
Kiedyś robiłem coś podobnego w C dla grafu z kilkoma milionami węzłów i implementacja oparta o algorytm UnionFind działa bardzo szybko.

@Wyjasnienie: Ciężkie zadanie, więc ciężko wytłumaczyć...
Ale wytłumaczyłem na więcej niż jeden sposób.
Podałem przykład. Nawet Ty powinieneś go zrozumieć.

Wygląda prosto chyba że czegoś nie kumam. Z tego co rozumiem grupy się łączą jeśli tylko wystąpi jeden wspólny element. Tworzysz listę grup trójek i setów, do setów wrzucasz wszystkie znalezione liczby ze wszystkich trójek i iterujesz po trójkach. Dla każdej trójki szukasz grupy w której już wystąpiły takie liczby w secie i dopisujesz pozostałe dwie liczby do seta i trójkę do grupy.
Jak chcesz zoptymalizować złożeniowo kosztem pamięci to możesz zrobić mapę (Dictionary) liczb na znalezione grupy, wtedy nie musisz iterować tylko masz zduplikowane referencje na grupy i na końcu wyciągasz tylko unikatowe grupy. Wszystko zależy ile masz trójek, ile potencjalnie wychodzi grup i ile jest możliwych wartości w trójkach (zawsze 000 do 999? jeśli tak to może to być array)
Chyba dałoby się z tego zrobić jednolinijkowiec na Aggregate

@Wyjasnienie:

Chcę każdą grupę połączonych ze sobą trójkątów przenieść do nowej listy.

no to tak jak pisałem wyżej wydaje mi się dobrze, iterujesz po wierzchołkach, sprawdzasz dla każdego wierzchołka czy istnieje już grupa z nim powiązana, jeśli tak to się dopisujesz, jeśli nie to tworzysz nową, jeśli istnieją osobne grupy dla dwóch wierzchołków to je ze sobą łączysz:

int[] input = [
    000, 001, 002,
    000, 002, 005,
    002, 007, 005,
    005, 007, 011,
    005, 011, 014,
    011, 016, 014,
    018, 005, 014,
    018, 014, 023,
    023, 014, 026,
    027, 028, 029,
    027, 029, 000,
    029, 034, 000,
    036, 027, 000,
    036, 000, 041,
    041, 000, 044,
    014, 046, 047,
    014, 047, 027,
    047, 052, 027,
    026, 014, 027,
    026, 027, 059,
    059, 027, 036,
    044, 000, 005,
    044, 005, 068,
    068, 005, 018,
    072, 073, 074,
    073, 076, 074,
    073, 079, 076,
    081, 082, 083,
    081, 083, 086,
    086, 083, 089,
    086, 089, 092,
    092, 089, 073,
    092, 073, 098,
    089, 100, 073,
    102, 103, 104,
    102, 104, 107,
    108, 109, 110,
    110, 109, 113,
    110, 113, 102,
    082, 118, 083,
    082, 121, 104,
    121, 107, 104,
    082, 104, 118,
    129, 082, 131,
    131, 082, 134,
    134, 082, 137,
    098, 073, 140,
    140, 073, 072,
    140, 072, 146,
    146, 072, 109,
    146, 109, 108,
    153, 002, 001,
    153, 007, 002,
    153, 011, 007,
    153, 016, 011,
    153, 047, 046,
    153, 052, 047,
    153, 029, 028,
    153, 034, 029,
    177, 072, 074,
    177, 074, 076,
    177, 076, 079,
    177, 100, 089,
    177, 089, 083,
    177, 083, 118,
    177, 118, 104,
    177, 104, 103,
    177, 113, 109,
    177, 109, 072,
    207, 018, 023,
    207, 023, 026,
    207, 026, 059,
    207, 059, 036,
    207, 036, 041,
    207, 041, 044,
    207, 044, 068,
    207, 068, 018,
    231, 081, 086,
    231, 086, 092,
    231, 092, 098,
    231, 098, 140,
    231, 140, 146,
    231, 146, 108,
    231, 108, 110,
    231, 110, 102,
    231, 102, 107,
    231, 107, 121,
    231, 129, 131,
    231, 131, 134,
    231, 134, 137
];

var lookup = new Dictionary<int, ListRef<int[]>>();
foreach (var trojka in input.Chunk(3))
{
    ListRef<int[]>? groupRef = null;
    foreach (var x in trojka)
    {
        if (lookup.TryGetValue(x, out var currentGroupRef))
        {
            // jesli dwa wierzcholki odnosza sie do roznych list grup
            if (currentGroupRef.Ref != groupRef?.Ref)
            {
                if (groupRef is not null)
                {
                    // polacz je
                    currentGroupRef.Ref.AddRange(groupRef.Ref);
                    groupRef.Ref = currentGroupRef.Ref;
                }

                groupRef = currentGroupRef;
            }
        }
    }

    groupRef ??= new ListRef<int[]>();
    groupRef.Ref.Add(trojka);
    foreach (var x in trojka)
    {
        lookup[x] = groupRef;
    }
}

// wypisywanie
var result = lookup.Values.Select(v => v.Ref).Distinct().ToList();
foreach (var grupa in result)
{
    foreach (var trojka in grupa)
        Console.WriteLine($"{trojka[0]:000}, {trojka[1]:000}, {trojka[2]:000}");
    Console.WriteLine("-------");
}

class ListRef<T>
{
    public List<T> Ref = [];
}

daje 2 grupy:

000, 001, 002
000, 002, 005
002, 007, 005
005, 007, 011
005, 011, 014
011, 016, 014
018, 005, 014
018, 014, 023
023, 014, 026
027, 028, 029
027, 029, 000
029, 034, 000
036, 027, 000
036, 000, 041
041, 000, 044
014, 046, 047
014, 047, 027
047, 052, 027
026, 014, 027
026, 027, 059
059, 027, 036
044, 000, 005
044, 005, 068
068, 005, 018
153, 002, 001
153, 007, 002
153, 011, 007
153, 016, 011
153, 047, 046
153, 052, 047
153, 029, 028
153, 034, 029
207, 018, 023
207, 023, 026
207, 026, 059
207, 059, 036
207, 036, 041
207, 041, 044
207, 044, 068
207, 068, 018
-------
102, 103, 104
102, 104, 107
108, 109, 110
110, 109, 113
110, 113, 102
072, 073, 074
073, 076, 074
073, 079, 076
081, 082, 083
081, 083, 086
086, 083, 089
086, 089, 092
092, 089, 073
092, 073, 098
089, 100, 073
082, 118, 083
082, 121, 104
121, 107, 104
082, 104, 118
129, 082, 131
131, 082, 134
134, 082, 137
072, 073, 074
073, 076, 074
073, 079, 076
081, 082, 083
081, 083, 086
086, 083, 089
086, 089, 092
092, 089, 073
092, 073, 098
089, 100, 073
082, 118, 083
098, 073, 140
140, 073, 072
140, 072, 146
146, 072, 109
146, 109, 108
177, 072, 074
177, 074, 076
177, 076, 079
177, 100, 089
177, 089, 083
177, 083, 118
177, 118, 104
177, 104, 103
177, 113, 109
177, 109, 072
231, 081, 086
231, 086, 092
231, 092, 098
231, 098, 140
231, 140, 146
231, 146, 108
231, 108, 110
231, 110, 102
231, 102, 107
231, 107, 121
231, 129, 131
231, 131, 134
231, 134, 137
-------

Tak jak pisze @obscurity jeżeli te trójki można opisać grafem. To najprostsze co można zrobić, to stworzyć ten graf, a potem sprawdzic czy graf jest pójny, np. przeszukujac go w głab, i każdy nie odwiedzony, wieszchołek gdy rekuracje ma głebokosć zero to nowa grupa.

W końcu wprowadziłem do swojego projektu rozwiązanie problemu.

Niestety problem jest bardziej złożony niż same trójki intów, bo te trójki są powiązane z konkretnymi danymi (współrzędne wierzchołka, wektor normalny, kolor) i jakbym zaczął same numerki wspólnych wierzchołków trójkątów grupować, to bym stracił te powiązania.

Więc wprowadziłem klasę dla trójkątów:

    public class MeshTriangle
    {
        public List<Vector3> vertices = new List<Vector3>();
        public List<Vector3> normals = new List<Vector3>();
        public List<Color32> colors = new List<Color32>();

        public List<int> sharedVerticesIds = new List<int>();

        public void AddVert(Vector3 vertex, Vector3 normal, Color32 color, int sharedVertexId)
        {
            vertices.Add(vertex);
            normals.Add(normal);
            colors.Add(color);
            sharedVerticesIds.Add(sharedVertexId);

            // shared vertices are points where triangles connect to each other,
            // we store them to detect separate verts groups => mesh parts not connected to each other
        }

        public bool IsConnectedToOther(MeshTriangle other)
        {
            for (int i = 0; i < sharedVerticesIds.Count; i++)
            {
                if (other.sharedVerticesIds.Contains(sharedVerticesIds[i]))
                {
                    return true;
                }
            }

            return false;
        }
    }

A tutaj jak komuś chce się to jeszcze analizować, jest moja wersja metody (GetMeshObjects()) dzielącej siatkę na spójne bryły:

    public class MeshData
    {
        List<MeshTriangle> meshTriangles = new List<MeshTriangle>();

        const int VertsPerTriangle = 3;

        public List<Mesh> GetMeshObjects()
        {
            List<Mesh> result = new List<Mesh>();

            while (meshTriangles.Count > 0)
            {
                List<MeshTriangle> connectedTriangles = new List<MeshTriangle>();

                int connectedStartIdx = 0;
                int connectedEndIdx;

                connectedTriangles.Add(meshTriangles[0]);
                meshTriangles.RemoveAt(0);

                do
                {
                    connectedEndIdx = connectedTriangles.Count;

                    for (int connectedIdx = connectedStartIdx; connectedIdx < connectedEndIdx; connectedIdx++)
                    {
                        for (int trianglesIdx = meshTriangles.Count - 1; trianglesIdx >= 0; trianglesIdx--)
                        {
                            if (connectedTriangles[connectedIdx].IsConnectedToOther(meshTriangles[trianglesIdx]))
                            {
                                connectedTriangles.Add(meshTriangles[trianglesIdx]);
                                meshTriangles.RemoveAt(trianglesIdx);
                            }
                        }
                    }

                    connectedStartIdx = connectedEndIdx;
                }
                while (connectedEndIdx < connectedTriangles.Count);
                // if there are no new connected triangles, full triangles group is found

                result.Add(TrianglesToMesh(connectedTriangles));
            }

            return result;
        }

        static Mesh TrianglesToMesh(List<MeshTriangle> meshTriangles)
        {
            Mesh mesh = new Mesh();

            int allVertsCount = meshTriangles.Count * VertsPerTriangle;

            Vector3[] vertices = new Vector3[allVertsCount];
            Vector3[] normals = new Vector3[allVertsCount];
            Color32[] colors = new Color32[allVertsCount];
            int[] triangles = new int[allVertsCount];

            for (int triangleIdx = 0, meshVertIdx = 0; triangleIdx < meshTriangles.Count; triangleIdx++, meshVertIdx += 3)
            {
                MeshTriangle meshTriangle = meshTriangles[triangleIdx];

                for (int triangleVertIdx = 0; triangleVertIdx < VertsPerTriangle; triangleVertIdx++)
                {
                    vertices[meshVertIdx + triangleVertIdx] = meshTriangle.vertices[triangleVertIdx];
                    normals[meshVertIdx + triangleVertIdx] = meshTriangle.normals[triangleVertIdx];
                    colors[meshVertIdx + triangleVertIdx] = meshTriangle.colors[triangleVertIdx];
                    triangles[meshVertIdx + triangleVertIdx] = meshVertIdx + triangleVertIdx;
                }
            }

            mesh.vertices = vertices;
            mesh.normals = normals;
            mesh.colors32 = colors;
            mesh.triangles = triangles;

            return mesh;
        }
    }

Biorę pierwszy trójkąt z listy meshTriangles i przenoszę do listy connectedTriangles wszystkie trójkąty, które się z nim łączą (czy się łączą, sprawdza metoda MeshTriangle.IsConnectedToOther(MeshTriangle other)). Potem robię to samo dla wszystkich przeniesionych trójkątów i następnych przeniesionych trójkątów... coraz dalej odchodząc od pierwszego trójkąta, aż pierwotna lista trójkątów meshTriangles będzie pusta.

Dzięki tej operacji, po rozcięciu siatki płaszczyzną na dwie połowy, mogę uzyskać więcej niż dwa obiekty (górny i dolny).
Np. jak wrogowi jednym cięciem obcinam obie nogi, to nie są one ze sobą zespawane :]