Union Find Disjoint Sets

Grouping items by a pairwise relation discovered incrementally - "these two symbols moved together", "these two broker symbol aliases are the same underlying instrument", "these two trade tickets belong to the same synthetic position" - is exactly what a union-find structure is for: Union(a,b) merges two elements' groups, Find(x) reports which group x is currently in, and Connected(a,b) asks whether two elements ended up in the same group after however many Union() calls have happened so far. The naive version of this structure (each Union() just re-points one tree's root at the other, with no other bookkeeping) can degrade into one long chain if merges happen in an unlucky order - a hostile-case sequence of n-1 unions all merging into the same growing chain makes Find() on the far end O(n). This implementation carries both of the two standard optimisations, not just one: Path compression: once Find() locates a node's true root, it re-points every node visited along the way directly at that root, so a repeated Find() on any of them afterward is O(1). Union by rank: when merging two trees, the shorter one is always hung under the taller one's root (breaking ties by incrementing rank), which keeps every tree's height logarithmic in the number of elements no matter what order Union() is called in. Either optimisation alone still leaves a real, if smaller, degenerate case; the combination is what gives the textbook inverse-Ackermann amortised bound - a claim that would be dishonest to make with only one of the two in place, which is why this header carries both. Notes and limitations - Elements are plain integer indices 0..Capacity()-1, not strings or tickets directly - map a caller's own keys (symbol names, ticket numbers) to a dense integer index externally if needed. - There is no Split()/Undo() - once two sets are merged there is no way to separate them again short of a full Init() rebuild. This matches the real-world semantics being modelled (once two symbols are confirmed correlated in a session, un-merging them is not a union-find operation). - Find()'s iterative two-pass form (locate the root, then rewire the path) is used instead of the classic one-line recursive version deliberately - MQL4's default call stack is shallower than most native languages', and a long uncompressed chain (see the demo's 200-element example) could recurse to a depth this two-pass form never has to.

Script · MT4 · v1.0 · Free

Tags: Dashboards & Scanners · Gold (XAUUSD) · MT4 Script · MQL4 Source Code

MQL4 & MQL5 scripts · PolyMaria