# Essays/Odometer

## Introduction

The odometer function of a list of non-negative integers x counts from 0*x to x-1 . For example, the odometer function of x=:4 2 3 is:

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

The odometer function can be computed in a variety of ways.

## Base Representation

The odometer is the base x representation of i.*/x . Thus:

```odometer=: #: i.@(*/)
```

## Catalogue

The odometer is the opened ravelled catalogue of i.0{x,  i.1{x,  i.2{x,  etc.

```   i.&.> 4 2 3
┌───────┬───┬─────┐
│0 1 2 3│0 1│0 1 2│
└───────┴───┴─────┘

{ i.&.> 4 2 3
┌─────┬─────┬─────┐
│0 0 0│0 0 1│0 0 2│
├─────┼─────┼─────┤
│0 1 0│0 1 1│0 1 2│
└─────┴─────┴─────┘

┌─────┬─────┬─────┐
│1 0 0│1 0 1│1 0 2│
├─────┼─────┼─────┤
│1 1 0│1 1 1│1 1 2│
└─────┴─────┴─────┘

┌─────┬─────┬─────┐
│2 0 0│2 0 1│2 0 2│
├─────┼─────┼─────┤
│2 1 0│2 1 1│2 1 2│
└─────┴─────┴─────┘

┌─────┬─────┬─────┐
│3 0 0│3 0 1│3 0 2│
├─────┼─────┼─────┤
│3 1 0│3 1 1│3 1 2│
└─────┴─────┴─────┘

, { i.&.> 4 2 3
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─
│0 0 0│0 0 1│0 0 2│0 1 0│0 1 1│0 1 2│1 0 0│1 0 1│1 0 2│1 1 0│1 1 1│1 1 2│ ...
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─

> , { i.&.> 4 2 3
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
1 0 0
...

odometer1=: > @ , @ { @ (i.&.>"_)
```

## Copy and Reshape

```   i.&.> x
┌───────┬───┬─────┐
│0 1 2 3│0 1│0 1 2│
└───────┴───┴─────┘

*/\. }. x,1
6 3 1
*/ x
24

6 3 1 #&.> i.&.> x
┌───────────────────────────────────────────────┬───────────┬─────┐
│0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3│0 0 0 1 1 1│0 1 2│
└───────────────────────────────────────────────┴───────────┴─────┘
24 \$&> 6 3 1 #&.> i.&.> x
0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3
0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
|: 24 \$&> 6 3 1 #&.> i.&.> x
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
1 0 0
...

odometer2=: [: |: */ \$&> */\.@}.@(,&1) #&.> i.&.>
```

## Remainders of Quotients

```   */x
24
*/\.}. x,1
6 3 1
(i.24) <.@(%/) 6 3 1
0 0  0
0 0  1
0 0  2
0 1  3
0 1  4
0 1  5
1 2  6
1 2  7
1 2  8
1 3  9
1 3 10
1 3 11
2 4 12
2 4 13
2 4 14
2 5 15
2 5 16
2 5 17
3 6 18
3 6 19
3 6 20
3 7 21
3 7 22
3 7 23
4 2 3 |"1 (i.24) <.@(%/) 6 3 1
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
1 0 0
...

odometer3=: |"1 i.@(*/) <.@(%/) */\.@}.@(,&1)
```

## Repeated Stitching

```   0 1 ,/@:(,."0 _) 0 1 2
0 0
0 1
0 2
1 0
1 1
1 2
0 1 2 3 ,/@:(,."0 _) 0 1 ,/@:(,."0 _) 0 1 2
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
1 0 0
...

odometer4=: > @: (,/@:(,."0 _)&.>/) @: (i.&.>)
```

## Counting in Base x

```   count =: (| + }.@:(,&0)@:=)^:_ (+ -@# {. 1:)
x count 0 0 0
0 0 1
x count 0 0 1
0 0 2
x count 0 0 2
0 1 0
x count 0 1 0
0 1 1
x count^:(i.7) 0 0 0
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
1 0 0

odometer5=: 3 : 'y count^:(i.*/y) 0*y'
```

## Sparse Array

```odometer6=: (4 \$. \$.)@(\$&1)  NB. contributed by David Ward Lambert
```

## Collected Definitions

```odometer =: #: i.@(*/)
odometer1=: > @ , @ { @ (i.&.>"_)
odometer2=: [: |: */ \$&> */\.@}.@(,&1) #&.> i.&.>
odometer3=: |"1 i.@(*/) <.@(%/) */\.@}.@(,&1)
odometer4=: > @: (,/@:(,."0 _)&.>/) @: (i.&.>)

count    =: (| + }.@:(,&0)@:=)^:_ (+ -@# {. 1:)
odometer5=: 3 : 'y count^:(i.*/y) 0*y'

odometer6=: (4 \$. \$.)@(\$&1)
```

## Some Applications of Odometer

All divisors of a positive integer:

```   divisors=: (*/ .^"1 odometer@:>:)/ @: (__&q:)

divisors 160
1 5 2 10 4 20 8 40 16 80 32 160
```

There is a simple relationship between odometer on n-i.n and the set of all permutations of i.n . See the Permutation Index essay.

```   a=: 215 275 335 355 420 580
n=: 1 + <. 1505 % a
n
8 6 5 5 4 3

s=: (1505 = t +/ .* a) # t=: odometer n
s
1 0 0 2 0 1
7 0 0 0 0 0
s +/ .* a
1505 1505
```

That is, \$15.05 worth of appetizers obtains by 1 mixed fruit, 2 hot wings, and 1 sampler plate, or by 7 mixed fruits.