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
