minimum spanning tree lua HPPL

[robmio]

(11-02-2021 11:57 AM)Albert Chan Wrote:  Version 3 assumed all edges vaild, unless specified otherwise.
I think the speed is due to not spend time to validate edges.

By shuffling mapped indexes, it keep the points to examine low.
Points to examine reduced to about 1/3 (and, no code to validate vertices)

Note: test for member in list has O(n)

---

Points examined, for oringinal Lua code, n = total points, k = vertices examined

sum(n*k, k=1..n-1)
= n * n*(n-1)/2
= n^3/2 - n^2/2

Points examined, with shuffled indexes, splitting off vertices and non-vertices.

sum((n-k)*k, k=1..n-1)
= sum((n-1)*k - k*(k-1), k=1..n-1)       // see Funny Factorials and Slick Sums
= (n-1) * n*(n-1)/2 - n*(n-1)*(n-2)/3
= n*(n-1)*(n+1)/6
= n^3/6 - n/6

Good. I'll try to translate your algorithm into Python, to see if it gets even faster. Thanks for your help.