Cómo determinar el número total de triángulos degenerados sin bucles de una longitud determinada (más de 3)

Encontrar un algoritmo O (n ^ 3) es bastante fácil y se puede hacer en pocas líneas, pero encontrar un algoritmo O (n ^ 2) es un poco más difícil. Aquí hay una posible solución que escribí rápidamente en F # que debería ejecutarse en tiempo O (n ^ 2):

Comparación de tipos = Menor | Igual | Mayor

// Función genérica útil para muchos problemas.
// Asume que slistA y slistB están ordenados y que comp es monótono.
// Utiliza esto para encontrar todos los pares “Iguales” en el tiempo O (longitud (slistA) + longitud (slistB)).
let rec scanCompare comp slistA slistB =
partido (slistA, slistB) con
| (x :: xs, y :: ys) -> // Divide slistA en el primer elemento xy el resto xs. Lo mismo para slistB. Cae al siguiente caso si alguno está vacío.
emparejar comp xy con
| Menor -> scanCompare comp xs slistB // Avanzar en ListA si su primer elemento es demasiado pequeño
| Mayor -> scanComparar comp slistA ys // Avanzar en ListB si su primer elemento es demasiado pequeño
| Equal -> (x, y): 🙁 scanCompare comp xs slistB) // Recopila el par de primeros elementos si comp devuelve “Equal”.
| _ -> [] // Devuelve cuando cualquiera de las listas de entrada está agotada.

let triangleCheck abc =
partido (a + b) – c con
El | x cuando x <0 -> Menor
El | x cuando x> 0 -> Mayor
| _ -> Igual

dejar degenTriangles sideslist =
let sortedlist = List.sort sidelist
[para x en sortedlist -> scanCompare (triangleCheck x) sortedlist sortedlist] |>
List.concat |>
List.map (diversión (x, y) -> (yx, x, y))

degenTriangles devuelve una lista de todos los triángulos posibles que se pueden construir combinando los elementos de sidesList, como tuplas con el lado más grande al final (contando las permutaciones de lados más pequeños dos veces). Ejemplo:

> degenTriangles [1; 2; 3; 8; 10; 14; 18; 19] ;;
val it: (int * int * int) list =
[(1, 1, 2); (1, 2, 3); (1, 18, 19); (2, 1, 3); (2, 8, 10); (8, 2, 10);
(8, 10, 18); (10, 8, 18); (18, 1, 19)]

Satisface el criterio de “no bucles” mediante el uso de la recursividad y la comprensión de listas.

Alternativamente, pero rompiendo el criterio de “no bucles”, aquí hay una versión optimizada de C ++ del mismo algoritmo escrito en un estilo más imperativo:

// Parte genérica del código que mantendría como funciones de biblioteca

enum class CompResult {menor, igual, mayor};

plantilla
T compareAccumulate (T init, InputIt firstA, const InputIt lastA, InputIt firstB, const InputIt lastB, TrinaryComparison comp, TrinaryOperation op)
{
while (firstA! = lastA && firstB! = lastB) {
switch (comp (* firstA, * firstB)) {
case CompResult :: less:
++ firstA;
descanso;
caso CompResult :: mayor:
++ firstB;
descanso;
caso CompResult :: igual:
init = op (* firstA, * firstB, init);
++ firstA;
}
}
return init;
}

plantilla
CompResult en línea trinComp (const T a, const T b)
{
si (a return CompResult :: less;
más si (a> b)
return CompResult :: mayor;
más
return CompResult :: igual;
}

// Parte específica del problema:

plantilla
int triangleCount (entrada std :: vector )
{
std :: sort (input.begin (), input.end ());
int suma = 0;
const auto end = input.end ();
T k;
for (auto i = input.begin (); i! = end; ++ i) {
k = * i;
sum + = compareAccumulate (0, i, end, i, end,
[k] (T x, T y) {return trinComp (x + k, y); },
[] (T a, T b, int x) {return x + 1; });
}
suma de retorno;
}

que es el doble que la versión F #, pero podría ser más fácil de leer si está acostumbrado a programas escritos en un estilo imperativo. Solo cuenta el número de triángulos en lugar de enumerarlos, y se ajusta para no contarlos dos veces. Debe manejar entradas de unos pocos miles de elementos en menos de un segundo.