All Pairs Algorithm

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.

• http:Release/Source/eg/AllPairs.java