[Jprogramming] Selfdescribing Sequence

[Jose Mario Quintana]

The difficulty of using this approach to solve the original problem with the
constraints is that the 1000000000 size series is too big to hold.  However,
one can notice that the series is very redundant,

   (((sg@]^:[)&1 2 2)"0) 8  NB. Using Oleg's neat verb
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9 10 10 10 10 10

One could attempt to represent the series in a compact form, instead of
storing all the repetitions one could store instead the number of
repetitions for each number and the compact form series, for the example
above, becomes,

1 2 2 3 3 4 4 4 5 5

But, of course, by definition the compact form of the series is the series
itself.  There you go!
 
> bounces at jsoftware.com] On Behalf Of Oleg Kobchenko
> Sent: Monday, January 09, 2006 2:58 PM
> To: Programming forum
> Subject: RE: [Jprogramming] Selfdescribing Sequence
> 
> Noting that n = {:@v we obtain:
> 
>    sg=: , ({~ {:) # >:@{:
>    ,.<@((sg@]^:[)&1 2 2)"0 i.7
> +---------------------------------------------+
> |1 2 2                                        |
> +---------------------------------------------+
> |1 2 2 3 3                                    |
> +---------------------------------------------+
> |1 2 2 3 3 4 4 4                              |
> +---------------------------------------------+
> |1 2 2 3 3 4 4 4 5 5 5                        |
> +---------------------------------------------+
> |1 2 2 3 3 4 4 4 5 5 5 6 6 6 6                |
> +---------------------------------------------+
> |1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7        |
> +---------------------------------------------+
> |1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8|
> +---------------------------------------------+
> 
> 
> --- Jose Mario Quintana <JoseMarioQuintana at 2BestSystems.Com> wrote:
> 
> > > bounces at jsoftware.com] On Behalf Of Randy MacDonald
> > > Sent: Monday, January 09, 2006 10:47 AM
> > > To: Programming forum
> > > Subject: Re: [Jprogramming] Selfdescribing Sequence
> > >
> > > Presume you have the start of the sequence:
> > >
> > >     1 2 2 3 3
> > >
> > > How many 4's do you need? sequence[4] or 3 (I'm using origin 1; old
> APL
> > > habit)
> > >
> > > Then the sequence is
> > >
> > >    1 2 2 3 3 3 4 4 4
> > >
> > > How many 5's? 3
> > >
> > >    1 2 2 3 3 4 4 4, 5 5 5
> > >
> > > NB. 1 2 2 3 3 4 4 4 = nextSDS 1 2 2 3 3
> > >
> > > If you can see where this is going, the algorithm presents itself:
> > >
> > > To get the i'th element (origin-1)
> > >
> > >    (>: i){ nextSSQ^:(i&>@$) 1 2 2
> > >
> > > ... if ^: takes a verb on the right (it used to, I might be henked on
> > > this)
> > >
> >
> >    n=. 0&{::
> >    v=. 1&{::
> >
> >    sg=. (<@:(n + 1:) 0} ])@:(<@:(v , (n{v) # n + 1:) 1} ]) f.
> >
> >    (sg@]^:[)&(2;1 2 2) i.7
> > +-+---------------------------------------------+
> > |2|1 2 2                                        |
> > +-+---------------------------------------------+
> > |3|1 2 2 3 3                                    |
> > +-+---------------------------------------------+
> > |4|1 2 2 3 3 4 4 4                              |
> > +-+---------------------------------------------+
> > |5|1 2 2 3 3 4 4 4 5 5 5                        |
> > +-+---------------------------------------------+
> > |6|1 2 2 3 3 4 4 4 5 5 5 6 6 6 6                |
> > +-+---------------------------------------------+
> > |7|1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7        |
> > +-+---------------------------------------------+
> > |8|1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8|
> > +-+---------------------------------------------+
> 
> 
> 
> 
> __________________________________________
> Yahoo! DSL - Something to write home about.
> Just $16.99/mo. or less.
> dsl.yahoo.com
> 
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm