MATtours of discrete mathematics

Odometer method

The odometer method for listing strings systematically uses theanalogy of a car or bicycle odometer.

An odometer consists of several wheels, each of which is marked with digits0 through 9. As the vehicle moves, each wheel turns through those digits.When it flips from 9 to 0, it advances the next wheel to the left by onedigit. A three-wheel bicycle odometer as a whole will read

000
001
002
003
. . .
009
010
011
012
. . .
019
020
021
. . .
099
100
101
102
. . .
999
000

To use the odometer method to list all strings of terms from the sequence 0, 1, 2, you imagine these numbers only on three wheels that turn the sameway. When a wheel flips from 2 to 0, it advances the next wheel to the leftby one digit:

000
001
002
010
011
012
020
021
022
100
101
102
110
111
112
120
121
122 200
201
202
210
211
212
220
221
222

To list all strings of terms from the sequence Q, E, D, you can consider the letters inalphabetical order or in the order given. Here's an example of the latter:

Q Q Q
Q Q E
Q Q D
Q E Q
Q E E
Q E D
Q D Q
Q D E
Q D D
E Q Q
E Q E
E Q D
E E Q
E E E
E E D
E D Q
E D E
E D D
D Q Q
D Q E
D Q D
D E Q
D E E
D E D
D D Q
D D E
D D D

Modifying the odometer

When you're trying to list strings systematically with limited repetition,as with permutations, a modified odometer method can be useful. You follow the odometer method but ignore those strings in which repetition(more than in the original sequence) arises.

With the starting sequence 1, 2, 3, 4, for example, the modified odometer method gives these permutations:

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2 2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1 3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1 4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

With the letters Q, E, E, D, the modified odometer method (beginning with the letters in alphabetical order) gives 12 permutations:

D E E Q
(Q flips to D; the second E flips to Q; ignore repetition in DEQD; advance last D to E)
D E Q E
(last E advances to Q, then flips to D; Q flips to D; E advances to Q; the first D advances to E; the last D advances to E)
D Q E E
(same as above until Q in second slot flips to D, advancing first D to E; third slot advances to E, and last slot advances all the way to Q to avoid repetition )
E D E Q
(and so on)
E D Q E
E E D Q
E E Q D
E Q D E
E Q E D
Q D E E
Q E D E
Q E E D