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:

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.

From http://xkcd.com/287/

   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.