As it turns out, my simple substitution appears to have been mistaken: it
happened to work for 3 but fails for 4. It looks like the "2&^." argument
to "under" does not vary according to the base. So, the base-n Gray code
generator can be implemented like this:
baseNGray=: 4 : '([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<i.x) ,~ x <@^ ]
((($~ *)@- +:@{:) , |.@]) i.@<.&.(2&^.)) y'
We can check that a sequence of Gray codes differs by only one digit in
adjacent positions:
*./1=+/"1]2~:/\(5$5)#:5 baseNGray 5
1
and that this sequence has no duplicates:
(#=#@:~.) 5 baseNGray 5
1
and that we have a full sequence:
(^~ = [: # baseNGray~) 5
1
On Mon, Dec 23, 2013 at 12:19 AM, Raul Miller <[email protected]> wrote:
> One issue is this:
>
> i.@<.&.(3&^.)
>
> Notice that 3%^. is the right verb for the under conjunction. There's
> no simple way of passing the 3 in as an argument to that verb.
>
> Does that make sense?
>
> Thanks,
>
> --
> Raul
>
>
> On Sun, Dec 22, 2013 at 10:28 PM, Devon McCormick <[email protected]>
> wrote:
> > Hi Everybody -
> >
> > I was recently thinking of a possible use for Gray codes that work in a
> > base greater than 2. Searching my mail on this, I was led back to a
> > discussion from 2006 that Dan Bron had kicked off by offering the
> > generation and conversion of Gray codes as a puzzle.
> >
> > R. E. Boss, among others, took this and ran with it, resulting in this
> set
> > of solutions:
> >
> http://www.jsoftware.com/jwiki/RE%20Boss/Performance%20Records/Gray%20code.
> >
> > Alas, these were all for binary Gray codes but I want one that works in
> > base 3, so I looked at the 0th-place entry on Mr. Boss's list (wrapped
> line)
> > :
> >
> > ([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<0 1) ,~ 2: <@^ ] ((($~ *)@-
> > +:@{:) , |.@]) i.@<.&.(2&^.))
> >
> > And thought, do I really have to fully understand this to convert it from
> > base 2 to base 3? It turns out, I don't. Simply by replacing the 2s
> with
> > 3s (and the "0 1", which appeared to be "i.2", with "0 1 2"), I came up
> > with this:
> >
> > ([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<0 1 2) ,~ 3: <@^ ] ((($~
> *)@-
> > +:@{:) , |.@]) i.@<.&.(3&^.))
> >
> > Applying this to an argument to see what I get:
> >
> > ([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<0 1 2) ,~ 3: <@^ ] ((($~
> *)@-
> > +:@{:) , |.@]) i.@<.&.(3&^.)) 3
> > 0 1 2 5 4 3 6 7 8 17 16 15 12 13 14 11 10 9 18 19 20 23 22 21 24 25 26
> >
> > I get a promising result as it appears to be a permutation of i.3^3; this
> > is the solution in "decimal" form. Converting this to base 3 confirms my
> > suspicion that this actually worked:
> >
> > 3 3 3#:([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<0 1 2) ,~ 3: <@^ ]
> > ((($~ *)@- +:@{:) , |.@]) i.@<.&.(3&^.)) 3
> > 0 0 0
> > 0 0 1
> > 0 0 2
> > 0 1 2
> > 0 1 1
> > 0 1 0
> > 0 2 0
> > 0 2 1
> > 0 2 2
> > 1 2 2
> > 1 2 1
> > 1 2 0
> > 1 1 0
> > 1 1 1
> > 1 1 2
> > 1 0 2
> > 1 0 1
> > 1 0 0
> > 2 0 0
> > 2 0 1
> > 2 0 2
> > 2 1 2
> > 2 1 1
> > 2 1 0
> > 2 2 0
> > 2 2 1
> > 2 2 2
> >
> > Rather amazing, don't you think?
> >
> > However, in addition to my refusal to understand the code before I
> modified
> > it, I'm faced with my inability to grasp why I can't simply generalize
> > this into a dyadic verb. I know enough to be suspicious that the "2:" or
> > "3:" is problematic, and when I try my usual crutch of "13 :", it
> confirms
> > that there is some kind of bump in the road from explicit to tacit:
> >
> > 13 : '([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<i.x) ,~ x <@^ ] ((($~
> > *)@- +:@{:) , |.@]) i.@<.&.(x&^.)) y'
> > 4 : '([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<i.x) ,~ x <@^ ] ((($~ *)@-
> > +:@{:) , |.@]) i.@<.&.(x&^.)) y'
> >
> > Though this answer is functionally correct, it's not tacit:
> >
> > 3 (4 : '([:>[:(({. * #@]) ,@:+ ($ (,: |.)))&.>/ (<i.x) ,~ x <@^ ]
> ((($~
> > *)@- +:@{:) , |.@]) i.@<.&.(x&^.)) y') 3
> > 0 1 2 5 4 3 6 7 8 17 16 15 12 13 14 11 10 9 18 19 20 23 22 21 24 25 26
> >
> > Can anyone explain to me why "13 :" fails, or how one might retain the
> > tacit structure with the conversion to the dyadic version?
> >
> > Also, there's actually a flaw in my working solution above as a better
> > sequence would wrap from the last to the first as a Gray code too.
> Though
> > this is an additional constraint not in the original puzzle, it is a
> useful
> > one. For example, a good sequence for two base-3 digits would be this:
> >
> > 00
> > 01
> > 02
> > 22
> > 20
> > 21
> > 11
> > 12
> > 10
> >
> > In this case, the last "10" Gray-codes to "00", the initial one.
> >
> > Any ideas on any of these questions?
> >
> > Thanks,
> >
> > Devon
> > --
> > Devon McCormick, CFA
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
--
Devon McCormick, CFA
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
