J's stack is a C stack and is limited in depth. J lists do not have
any such limits.
J primitives are designed with significant constant time overhead, but
low cost for handling large amounts of data.
In other words you can do things the way you describe, but J favors
analytic approaches over arbitrary low-level modularity.
That said, I think you might be able to use something like this:
(#~ P"1)@([: ,/ ,"1 0/&'abc')^:_(1 0$'')
Here, I'm assuming that P"1 returns a 1 or a 0 for each of the strings
to be considered.
This isn't quite right, though, because it doesn't handle termination properly.
A simple way to avoid that problem is to maintain some state:
monitor@(#~ P"1)@([: ,/ ,"1 0/&'abc')^:_ LONGEST=:1 0$''
where
monitor=:3 :'if. #y do. LONGEST=: y else. LONGEST end.'
You can also extend this function to conditionally display
intermediate results (for example when 0={:$y). You may want to only
display the first row of y here.
Note also that this assumes either heavy pruning of results, or that
you have enough memory to store all results of the same length.
Using induction instead of recursion avoids problems with stack depth.
I hope this helps,
--
Raul
On Wed, Jun 26, 2013 at 6:52 PM, Mike Müller <[email protected]> wrote:
> In the application I have in mind P(w) means that some pattern does not occur
> in the string.
> Therefore this has to be also true for all the prefixes. Sorry for not
> specifying this properly in my first mail.
> So in this case I'm looking for a solution of type (b) I assume.
>
> I have a feeling that I should be able to almost literally translate this
> ruby-piece to J using ` and @.,
> in a simpler fashion than the examples in the knightstour page, but so far
> all my attempts didn't work.
> Do I really need to simulate the stack myself? Shouldn't this be taken care
> of by J if I do a simple recursion?
>
> I'm doing this kind of searching for strings quite often with different
> properties P,
> but in all of them P has to be true for all prefixes as well.
> Thus I would just like to create some sort of template in J (like this
> bk-procedure), where I can plug in different verbs P.
>
> I hope I have cleared things up a bit and thank for all the advice so far!
>
> Mike
>
> Am 26.06.2013 um 15:58 schrieb Raul Miller <[email protected]>:
>
>> On Wed, Jun 26, 2013 at 4:37 AM, Mike Müller <[email protected]> wrote:
>>> I hope this is not too simple a question for this list, but I'm still
>>> learning J and wonder how to do a simple backtracking in J.
>>> For instance, I might want to see what is the longest string consisting of
>>> a,b, and c, that fulfills some property P.
>>> In any imperative language (here: ruby) I would do something like this…
>>>
>>> def bk(w)
>>> if (!P(w)) return
>>> bk(w+"a")
>>> bk(w+"b")
>>> bk(w+"c")
>>> end
>>> bk("")
>>>
>>> …and combine it with some bookkeeping of which was the longest that I've
>>> seen so far and maybe some output every 100 steps,
>>> if there is actually no longest one (that is, there is an infinite one
>>> fulfilling P).
>>>
>>> I'm very interested how to do these kind of things elegantly in J.
>>
>> One simple way to do these kinds of things elegantly in J involves
>> calling out to some other language to do them in.
>>
>> Put differently, as described, this strikes me as a "solution looking
>> for a problem" - it's a rigged game.
>>
>> Note also that your definition of bk conflicts with the problem you
>> say you are trying to solve. It only finds strings where all prefixes
>> of the string also satisfy P. If there's a longer string which
>> satisfies P but which has a prefix which does not satisfy P then bk
>> would not find it.
>>
>> With those cautions out of the way, I think that an elegant solution
>> in J would either:
>>
>> (a) exhaustively test all the possibilities up to some resource
>> constrained limit (that leaves you with modularity - you can be
>> completely ignorant of the properties of P and have a simple solution
>> this way, as long as the resource constraints don't hurt you)
>>
>> (b) incorporate knowledge about P() in the search itself. (That's
>> essentially what you have done here, with bk, if bk is a valid
>> solution.)
>>
>> Does this make sense? Do you think I've overlooked an important point?
>>
>> (Note also that for exponential growth problems it often makes sense
>> to start with small trials and work your way up. If the problem grows
>> rapidly enough, the cost of exploring restricted cases can be
>> trivial.)
>>
>> Thanks,
>>
>> --
>> Raul
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
