Essays/Odometer
< Essays
Jump to navigation
Jump to search
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.
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.
See also
Contributed by Roger Hui.