Just another Perl shrine | |
PerlMonks |
Re^2: Extendable pairwise indexes - prior work?by pjf (Curate) |
on Apr 02, 2007 at 07:27 UTC ( [id://607769]=note: print w/replies, xml ) | Need Help?? |
My apologies, I probably should have included an example. The important thing to note is that since we're storing information on unordered pairs, so that (0,1) is the same as (1,0). Hence the requirement that X > Y to find the index allows us to cover all possible pairs:
Which provides the output: Info for pair (1, 0) is stored at: 0 Info for pair (2, 0) is stored at: 1 Info for pair (2, 1) is stored at: 2 Info for pair (3, 0) is stored at: 3 Info for pair (3, 1) is stored at: 4 Info for pair (3, 2) is stored at: 5 Info for pair (4, 0) is stored at: 6 Info for pair (4, 1) is stored at: 7 Info for pair (4, 2) is stored at: 8 Info for pair (4, 3) is stored at: 9 Info for pair (5, 0) is stored at: 10 Info for pair (5, 1) is stored at: 11 Info for pair (5, 2) is stored at: 12 Info for pair (5, 3) is stored at: 13 Info for pair (5, 4) is stored at: 14 The important thing to note here is that as the range expands we're able to encode the additional pairs created by the addition of extra elements into our potential array. As a simple example, I'm using this to store information about undirected graphs, where every vertex may contain a link to any other vertex, and the graph can grow over time. By using the algorithm described above we can encode the entire graph as a bitstring, with each position indicating the presence (true) or absence (false) of an edge between two nodes. The whole thing works just fine, but I'm certain it's not an original algorithm, hence my seeking of wisdom before anything goes up on the CPAN.
Paul Fenwick Perl Training Australia
In Section
Seekers of Perl Wisdom
|
|