All Pairs Algorithm


http:run.cgi

We can setup any sized problem. As is the tradition, columns are variables. Here we setup three variables with five elements in the largest.

eg.AllPairs$Setup
a p x
b q y
c r  
d   

We maintain a list of pairs, ordered with the most desired first. We measure desire by computing a rank, which will change as we fill pairs into cases.

eg.AllPairs$Pairs
left right used rank()
a p   
a q   
a r   
a x   
a y   
b p   
b q   
b r   
b x   
b y   
c p   
c q   
c r   
c x   
c y   
d p   
d q   
d r   
d x   
d y   
p x   
p y   
q x   
q y   
r x   
r y   

Here we step through the filling process. This is slow going because many of the pairs we retrieve from the list (using next()) don't fit the case we're assembling.

eg.AllPairs$Step
next() rank() isFit() hold() slug() isFull()
   true   a,p,null false
   false   a,p,null false
   false   a,p,null false
   true   a,p,x true
   true   a,q,null false
   false   a,q,null false
   true   a,q,y true
   true   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   false   a,r,null false
   true   a,r,x true
   true   b,p,null false
   false   b,p,null false
   false   b,p,null false
   true   b,p,x true

Now we step a little faster by substituting nextFit() for next().

eg.AllPairs$Step
nextFit() rank() isFit() hold() slug() isFull()
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true
   true 0   false
   true 0   true

Let's look at those pairs again and see how the used count and rank() have changed.

eg.AllPairs$Pairs
left right used rank()
a p   
a q   
a r   
a x   
a y   
b p   
b q   
b r   
b x   
b y   
c p   
c q   
c r   
c x   
c y   
d p   
d q   
d r   
d x   
d y   
p x   
p y   
q x   
q y   
r x   
r y   

Want to go faster still? Here is a fixture that runs out the rest of the cases and shows us everything.

eg.AllPairs$Cases
number items
1  
2  
3  
4  
5  
6  
7  
8  
9 
10  
11  
12  
13  
14  
15  
16  


Let's try the same setup but not single step it. This will be a check to make sure our stepper isn't messing up the sequence.

eg.AllPairs$Setup
a p x
b q y
c r  
d   

eg.AllPairs$Cases
number items
1  
2  
3  
4  
5  
6  
7  
8  
9 
10  
11  
12  
13  
14  
15  
16  


Ok. This is fun. Let's try some fun data.

eg.AllPairs$Setup
Mrs Peacock Library Rope
Colonel Mustard Conservatory Knife
Miss Scarlet Kitchen Gun
Professor Plum   

eg.AllPairs$Cases
number items
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  


Want to go really really fast? Here we generate setups based on only the desired number of items in each variable. Then cases() counts the generated cases. It also leaves a pairs count and elapsed msec by side effect.

eg.AllPairs$Stats
items cases() pairs msec
1,1 1   
1,2 2   
2,1 2   
2,2 4   
2,2,2    
2,2,2,2    
2,2,2,2,2    
1,2,1,2,1,2,1,2,1,2,1    
10,10 100   
10,10,2,2,2    
10,10,4,2,2    
10,10,4,4,2    
10,10,4,4,4    
4,4,4,10,10    


See the source.

fit.Summary

 

Last edited November 4, 2002
Return to WelcomeVisitors