Zbieranie grupy zbiorów 3-elementowych,

Zbieranie grupy zbiorów 3-elementowych,
Spine
  • Rejestracja:prawie 22 lata
  • Ostatnio:28 minut
  • Postów:6616
0

Dana jest lista liczb całkowitych:

Kopiuj
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#.


🕹️⌨️🖥️🖱️🎮
YA
  • Rejestracja:prawie 10 lat
  • Ostatnio:około godziny
  • Postów:2363
3

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.

Spine
  • Rejestracja:prawie 22 lata
  • Ostatnio:28 minut
  • Postów:6616
0

@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ć.


🕹️⌨️🖥️🖱️🎮
edytowany 1x, ostatnio: Spine
WY
Nie rozumiem wytłumacz logicznie, normalnie jak byś to na kartce papieru rozwiązał, czy matematycznie zapisał wtedy to rozwiążę, tak kompletnie nie rozumiem o co chodzi w tym problemie.
obscurity
  • Rejestracja:około 6 lat
  • Ostatnio:około 3 godziny
0

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


"A car won't take your job, another horse driving a car will." - Horse influencer, 1910
edytowany 3x, ostatnio: obscurity
Spine
  • Rejestracja:prawie 22 lata
  • Ostatnio:28 minut
  • Postów:6616
0

@Wyjasnienie:
Notepad2_1.png

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


🕹️⌨️🖥️🖱️🎮
edytowany 1x, ostatnio: Spine
obscurity
  • Rejestracja:około 6 lat
  • Ostatnio:około 3 godziny
3

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:

Kopiuj
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:

Kopiuj
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
-------

"A car won't take your job, another horse driving a car will." - Horse influencer, 1910
FA
  • Rejestracja:około 5 lat
  • Ostatnio:2 minuty
  • Lokalizacja:warszawa
  • Postów:301
1

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.

Spine
  • Rejestracja:prawie 22 lata
  • Ostatnio:28 minut
  • Postów:6616
0

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:

Kopiuj
    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:

Kopiuj
    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 :]
screenshot-20240219022428.png


🕹️⌨️🖥️🖱️🎮
edytowany 1x, ostatnio: Spine
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)