# Loopless Ruler

This function (based on Algorithm L for loopless Gray code generation in TAOCP 7.2.1.1):

```void ruler(int n)
{
int f[n+1];
for (int j = 0; j <= n; j++) {
f[j] = j;
}
while(true) {
visit(f,n+1);
int j = f[0];
f[0] = 0;
if (j == n) break;
f[j] = f[j+1];
f[j+1] = j+1;
}
}
```

enables us to compute the “ruler function”, ρ for 1, 2, 3…:

```0 1 0 2 0 1 0 3 0 1 0 2 0 1 0...
```

It’s a “loopless” algorithm and uses f, an array of “focus pointers” to keep track of what’s going on.

The ruler function ρ(n) is essentially the number of trailing 0’s in the binary representation of n.

This is what’s printed by ruler(4):

```0 1 2 3 4
1 1 2 3 4
0 2 2 3 4
2 1 2 3 4
0 1 3 3 4
1 1 3 3 4
0 3 2 3 4
3 1 2 3 4
0 1 2 4 4
1 1 2 4 4
0 2 2 4 4
2 1 2 4 4
0 1 4 3 4
1 1 4 3 4
0 4 2 3 4
4 1 2 3 4
```

The left hand side is the ruler function of course, what are the other values?

It’s clearer if we print f in reverse and match up with binary representations:

```00000
43210
00001
43211
00010
43220
00011
43212
00100
43310
00101
43311
00110
43230
00111
43213
01000
44210
01001
44211
01010
44220
01011
44212
01100
43410
01101
43411
01110
43240
01111
43214
```

If n[j] is the jth binary digit of n, then f[j] is just j, unless n[j] is the first of a block of 1’s, in which case f[j] is the index of the first 0 after that block.

For example, 01101, has block starting at 0 and ending at 1, so f[0] = 1, and another block starting at 2, ending at 4, so f[2] = 4; for other j, f[j] = j, so the focus pointers are 43411.

If n is of the form:

```j   k
01110111
```

with f[0] = k, f[k] = k, f[k+1] = j

0n incrementing we get:

```j   k
01111000
```

Now f[0] = 0, f[k] = j and f[k+1] = k+1, other values of f are the same

If k is 0, then we go from:

```j   k
01110
```

with f[0] = 0, f[1] = j

to:

```j   k
01111
```

with f[0] = 0, f[1] = 1

Either way, we can see that the inner loop of `ruler` is correct.