It used to be call "back-tracking", which I also liked to think of as generalised counting when I rediscovered it. A lot of elementary combinatorial algorithms, eg. generating permutations, combinations, etc. are usefully regarded in this way --- especially when having to be recoded in yet another language on the umpteenth occasion ... WFL On 6/29/20, Steve Witham <sw@tiac.net> wrote:
Counting in decimal is analogous to walking a tree. A tree of unbounded depth for that matter. "Carrying" is like popping the stack and going to another [[great...] grand] parent node. The higher digits are further *up* the tree and it just keeps going up... I'm getting hypoxia just thinking about it.
Grade-school kids (me included) eventually learn to count without a lot of thinking.
In contrast I find tree-traversals (usually implicit) one of the most awkward tasks in programming. I mean depth-first. Even when the number of levels is fixed, even when it's shallow enough to use recursion in a language with a limited stack. The bookkeeping, the program structure are just awkward.
Even in Prolog (where depth-first tree search is everything) it might make a program a bit scattered-looking. Well let's try. (I'm making up a dialect of Prolog here. "(car : cdr)" shall mean cons.)
(Decimal (d)) if (Digit d). (Digit d) if (Element d (0 1 2 3 4 5 6 7 8 9)). (Decimal (d : n)) if (NZDigit d) and (ZDecimal n). (NZDigit d) if (Element d (1 2 3 4 5 6 7 8 9)). (ZDecimal (d)) if (Digit d). (ZDecimal (d : n)) if (Digit d) and (ZDecimal n).
But all that aside, the digit-counting analogy sounds like a nice way to organize a tree search or a very-nested loop. Have an array of digit positions, and at each position a sub-array of possibilities. Then have a parallel array of indexes into those arrays. So, each time through the loop you increment the bottom digit with carry. Easy peazy, heh.
(I'm currently writing a test for a module with a big cross-product of test cases.)
--Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun