# 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 5, 2002