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
