in reply to Re^2: Link Connectivity Algorithim
in thread Link Connectivity Algorithim

So what *is* allowed? Can you have 'a|b' => 'b|c'? Can you have 'a|b' => 'b|a'? Can you have 'a|b|c' => 'x|y'? 'a|b' => 'x|y|z'? Be more specific on the constraints. (Your constraints will make the difference between a cubed, O(n log n) or a linear solution, so they are important).

Replies are listed 'Best First'.
Re^4: Link Connectivity Algorithim
by dunkirk_phil (Novice) on Oct 30, 2006 at 13:55 UTC
    Basically the key matches its value, so even 'a|b => b|a' is illegal. Also the size of the key/value is 2. So values like 'a|b|c' are illegal because its size is deemed as 3.
[reply]
      If the value has to match the key, the values are redundant. You may as well specify an array.

      However, it's clear that the above rules aren't complete. After all, 'a|b', 'b|c', 'b|d', is illegal, yet all values contain two points.

      It could very well be that all you require is an implementation of a Union-Find algorithm (which runs in time O(N ack-1N)), but without a good specification, we can't be sure.

[reply]

In Section Seekers of Perl Wisdom