Какой алгоритм должен быть для построения треугольников?

Question

[Дмитрий Самутин]

Имеется лист массивов строк(List<string[]>), где каждый элемент листа состоит из 2-х строк и является уникальным, а в паре не может быть двух одинаковых значений (не может быть "[Ntv, Ntv]"). Требуется создать лист уникальных треугольников, где вершины это значения пар. Необходим именно алгоритм, до которого я всё никак не могу допереть.

Пример готового треугольника:
Triangles.Add(new Triangle(X, Y, Z)), где X=[Ntv, Tbh], Y=[Vyt, Tbh], Z=[Vyt, Ntv]

Пример листа:

[
   [Ntv, Tbh],
   [Vyt, Tbh],
   [Roh, Vyt],
   [Roh, Ntv],
   [Vyt, Ntv]
   ...
]

Имеется код на C#, но он работает не корректно (есть повторяющиеся треугольника, у которых вершины имеют разную очередность).

Сам код:

List<string[]> pairs = new List<string[]>();
List<Triangle> Triangles = new List<Triangle>();
foreach (string x in pairs)
{
    string[] X = pairs;
    foreach (string y in pairs)
    {
        string[] Y = pairs;
        if ((X[0] == Y[0] || X[0] == Y[1] || X[1] == Y[0] || X[1] == Y[1]) && !Equals(X, Y))
        {
            foreach (string z in pairs)
            {
                string[] Z = pairs;
                if (
                    X[0] == Y[0] && ((Z[0] == X[1] && Z[1] == Y[1]) || (Z[1] == X[1] && Z[0] == Y[1])) ||
                    X[0] == Y[1] && ((Z[0] == X[1] && Z[1] == Y[0]) || (Z[1] == X[1] && Z[0] == Y[0])) ||
                    X[1] == Y[0] && ((Z[0] == X[0] && Z[1] == Y[1]) || (Z[1] == X[0] && Z[0] == Y[1])) ||
                    X[1] == Y[1] && ((Z[0] == X[0] && Z[1] == Y[0]) || (Z[1] == X[0] && Z[0] == Y[0]))
                    )
                Triangles.Add(new Triangle(X, Y, Z));
            }
        }
    }
}
Console.WriteLine(Triangles);
return Triangles;

Что у меня не так?

Comments

[longclaps]

Треугольники составляются из произвольных вершин или собираются из имеющихся отрезков (в качестве сторон)?

[Дмитрий Самутин]

longclaps, Из имеющихся в листе отрезков (в качестве сторон)

[Дмитрий Самутин]

longclaps, Спасибо. Переведу в шарп, попробую на своей гигантской таблице и отпишусь об успешности.

[longclaps]

Дмитрий Самутин, на хорошем языке писать приятнее, поэтому питончик:)

from collections import defaultdict

segments = [['Ntv', 'Tbh'],
            ['Vyt', 'Tbh'],
            ['Roh', 'Vyt'],
            ['Roh', 'Ntv'],
            ['Vyt', 'Ntv']]
neighbours = defaultdict(set)
for ab in segments:
    neighbours[min(ab)].add(max(ab))
aa = list(neighbours.keys())
for a in aa:
    for b in neighbours[a]:
        for c in neighbours[a] & neighbours[b]:
            print(a, b, c)

вот вывод:

Ntv Tbh Vyt
Ntv Roh Vyt

[Руслан .]

Каждый элемент списка, это точка, с координатами заданными двумя строками.
На выходе для каждого треугольника должны быть три разные точки, для которых нужно проверить, что они не лежат на одной линии (хотя в задаче этого явно не сказано)
И да тут задача переборная и для получения всех треугольников нужно пройтись по всем вариантам, но сложность меньше чем O(N^3).
Если все точки разные и никакие три из них не лежат на одной прямой, то для массива из 5 точек, будет
1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5

Количество треугольников - это количество сочетаний по 3 точки из 5 имеющихся, т.е.
C(5, 3) = 5!/(3!*2!) = 120/(2*6) = 10
В общем случае будет C(N,3) = N!/((N-3)!*3!), т.е. например для n = 1000 получим 166167000 треугольников

Т.е. перебор индексов элементов массива такой 1>=i>j>k<=N и тут точно не будут возникать дубли треугольников.
Единственный момент, реальные индексы нужно начинать с нуля и заканчивать на N-1
N - количество элементов массива.

Поэтому комментарий Rsa97 не плохое решение, тем более что более быстрого нет, перебор нужно выполнить полностью.

Answer 1

[Rsa97]

В принципе, ваш алгоритм рабочий, только перебирать надо не все отрезки в каждом цикле, а только те, что лежат ниже. То есть

for (i = 0; i < pairs.length-2; i++) {
  ... 
  for (i = i+1; j < pairs.length-1; j++) {
    ...
    for (k = j+1; k < pairs.length; k++) {
      ...
    }
  }
}

Comments

[longclaps]

... попробую на своей гигантской таблице

Плохая идея - О(N^3)