Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Extendable pairwise indexes - prior work?

by blokhead (Monsignor)
on Apr 04, 2007 at 01:46 UTC ( #608176=note: print w/ replies, xml ) Need Help??


in reply to Extendable pairwise indexes - prior work?

I would call this a special case of a ranking algorithm for combinations. An "unordered pair" as you have is simply a "subset of size 2" (or "combination of size 2"). A ranking algorithm is a 1-to-1 mapping from a set of N combinatorial objects to the integers {1...N}, with the additional property that it preserves some sort of "ordering" among the combinatorial objects.

In this case, your ranking algorithm preserves a form of lexicographic ordering. When you write the pairs as (M,N) with M>N, then you have that rank(M,N)<rank(R,S) if and only if (M,N) appears before (R,S) in lexicographic order. You may not actually use this property, but you got it for free. ;)

Look at the ranking algorithm I gave in Re: Sampling from Combination Space (for general combinations):

sub rank { my @comb = sort { $a <=> $b } @_; sum map { binomial( $comb[$_]-1, $_+1 ) } 0 .. $#comb; }
For combinations of size 2, ours both compute the same thing:
binomial(X,2)+binomial(Y,1) = X(X-1)/2 + Y
I got the algorithm from a PDF draft version of a textbook that may never get published (which would be a shame). That PDF is not available online anymore, but if you are curious, I can send you the copy I have archived (hopefully that's kosher). I would be surprised if these kinds of things don't also show up somewhere in Knuth TAoCP volume 4 (if it's out yet, that is), where it deals with the related topics of combinatorial generation.

blokhead


Comment on Re: Extendable pairwise indexes - prior work?
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://608176]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (10)
As of 2015-07-08 06:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (94 votes), past polls