[Zrig]

Quiero generar aletoriamente relación transitiva entre los primeros n números naturales. Para ello, primero creo una matriz triangular \( A = (a_{ij})_{0\leq i < j < n} \) y le asigno aleatoriamente valores verdadero/falso, de forma que \( a_{ij} \) = verdadero sii i está relacionado con j.
Para asegurarme que sea transivita, aplico el siguiente algoritmo:

FOR i=0 TO n-1
   FOR j=i+1 TO n-1
      FOR k=j+1 TO n-1
         IF \( a_{ij} \) AND \( a_{jk} \) THEN \( a_{ik} \) = TRUE

Juraría que es correcto, pero no lo es porque me ha generado (para n=6) una relación que no es transitiva.
¿Dónde está el error y cómo puede solucionarse?

[Masacroso]

Creo que el error está en que la rutina FOR cuando termina genera nuevos puntos los cuales deben volver a ser pasados por la rutina FOR, es decir, los \( a_{i,k} \) generados pueden no ser transitivos con otros puntos.

[Zrig]

Gracias por la respuesta Masacroso. La solución, entonces, es recomenzar el algoritmo cuando se cambia \( a_{ik} \). No parece muy eficiente pero al menos así tienes que salir sí o sí  .

[Masacroso]

Gracias por la respuesta Masacroso. La solución, entonces, es recomenzar el algoritmo cuando se cambia \( a_{ik} \). No parece muy eficiente pero al menos así tienes que salir sí o sí  .

No eficiente no es, habría que pensar otra solución. En programación la eficiencia es fundamental, habría que buscarse un procedimiento más lineal o directo.

[Luis Fuentes]

Hola

 En este documento se sugiere generar aleatoriamente una matriz de incidencia (complejidad \( O(n^2) \))

 Y luego hacer su clausura transitiva. En este otro documento se indican algortimos para hacer tal clausura de orden \( O(n^3) \).

http://cs.winona.edu/lin/cs440/ch08-2.pdf

Saludos.