This presentation is delivered by the Stanford Center for Professional Development.
Today I'm gonna keep talking a little bit more about another procedural recursion example and
then go on to talk about, kind of, the approach for recursive backtracking,
which is taking those procedural recursion examples and kind of twisting them around and doing new things with them. Okay.
This is the last problem I did at the end of
Wednesday's lecture. It's a very, very important problem, so I don't actually
want to move away from it until I feel that I'm getting some signs from you
guys that we're
getting some understanding of this because it turns out it forms the basis of a lot of
other solutions end up just becoming permutations, you know, at the core of it.
So it's
a pretty useful pattern to have [inaudible]
list the permutations of a string. So you've got the string, you know, A B C D, and it's
gonna print all the A C D A B C D
A variations that you can get by rearranging all the letters.
It's a deceptively short piece of
code that does what's being done here
-is that it breaks it down in terms of there being the permutation that's
assembled so far, and then the remaining characters that haven't yet been looked
at, and so
at each recursive call it's gonna
shuffle one character from the
remainder onto the thing that's been chosen so far. So chose the next
character in the permutation, and eventually, when the rest is empty,
then all of the characters have been moved over, and have been laid down in
permutation, then what I have is a full permutation of the length end.
In the case where rest is not empty, I've still got some choices to make. The number of
choices is exactly equal to the number of characters I have left in
rest,
and for each of the remaining characters at this point, maybe there's just C
and D left,
then I'm gonna try each of them
as the next character in the permutation, and then permute what remains after
having made that choice.
And so this is
[inaudible] operations here of
attaching that [inaudible]
into the existing so far, and then subtracting it
out of the rest
to set up the arguments for that recursive call. A
little bit at the end we talked about this idea of a wrapper function where
the interface to list permutations from a client point of view probably just wants to
be, here's a string to permute
the fact that [inaudible]
keep this housekeeping of what I've built so far is really any internal management
issue, and isn't what I want to expose as part of the interface,
so we in turn have just a really simple one line translation that the outer
call just sets up and makes the call to the real recursive function setting up
the right state for the housekeeping in this case, which is the
permutation we've assembled at this point.
So
I'd like to ask you a few questions about this
to see if we're kind of seeing the same things. Can
someone tell me what is the first permutation that's printed by this
if I put in the string A B C D?
Anyone want to help me?
A B C D. A B C D. So the exact string I gave it, right, is the one that it picks, right,
the very first time, and that's because,
if you look at the way the for loop is structured, the idea is that it's gonna make a
choice and it's gonna move through the recursion. Well, the choice it always makes is to take
the next character of rest and attach it to the permutation
as its first time through the for loop. So the first time through the very first
for loop it's got A B C D to chose, it chooses A,
and now it recurs on A in the permutation and B C D to go. Well, the
next call does exactly the same thing, chooses the first of what remains, which
is B, attaches it to the permutation and keeps going.
So the kind of
deep arm of the recursion making that first choice and working its way down to
the base case, right, right remember the recursion always goes deep. It goes down to the end of
the
-and bottoms on the recursion before it comes back and revisits any previous
decision, will go A B C D,
and then
eventually come back and start trying other things, but that very first one,
right, is all just the sequence there.
The next one that's after it, right,
is A B D C,
which involved unmaking those last couple decisions.
If I look at
the tree that I have here that may help to sort of identify it.
That permute of emptying A B C,
the first choice it makes is go with A, and then the
first choice it makes here is go with B, and so on, so that the first thing that we can see
printed our here will be A B C D, we get to the base case.
Once it's tried this, it'll come back to this one, and on this
one it'll say, well, try the other characters. Well, there's no other
characters. In fact, this one also finishes.
It'll get back to here as it unwinds the stack the way the stack
gets back to where it was previously in these recursive calls. And now it says, okay,
and now try the ones that have,
on the second iteration of that for loop, D in the front,
and so it ends up putting A B D together,
leaving C, and then getting A B D C. And
then, so on kind of over here, the other variations, it will print all of the ones that have A
in the front.
There are eight of them.
I believe three, two
-no, six. Six of them
that have A in the front, and we'll do all of those. And only after having done all of
working out that whole part, which involves kind of the [inaudible] of this whole arm,
will eventually unwind back to the initial permute call,
and then say, okay, now try again. Go with B in the front and work your way
down from reading the A C D behind it.
So we'll see all the As
then the bunch that lead with B, then the bunch that leads with C, and then finally the
bunch that leads with D.
It doesn't turn out -matter, actually, what order it visits them in because, in fact, all we
cared about was seeing all of them. But part of what I'm trying to get with you
is the sense of being
able to look at that recursive code,
and use your mind to kind of trace its activity and think about the
progress that is made through those recursive calls. Just
let me look at that code just for a second more and see if there's any else that I want to
highlight for you.
I think that's about what
it's gonna do.
So if you don't understand this cost, if there's something about it that confuses you, now
would be an excellent time for you to ask a question that I could help
kind of get your understanding
made more clear. So
when you look at this code, you feel like you believe it works? You understand it? [Inaudible]. I have a question.
Is there a simple change you can make to this
code
so that it does combinations [inaudible]?
Does combinations -you mean, like, will skip letters?
Right. Yes. It turns out we're gonna make that change in not five minutes.
In effect, what you would do -and there's a pretty simple change with
this form. I'm gonna show you a slightly different way of doing it,
but one way of doing it would be to say,
well, give me the letter, don't attach it to next right? So right now, the
choices are pick one of the letters that remain and then attach it to
the permutation. Another option you could do was pick a letter and just discard it,
right? And so, in which case, I wouldn't add it into so far.
I would still subtract it from here, and I'd make another recursive call
saying, now
how about the permutations that don't involve A at all? And
I would just drop it from the thing and I would recurs on just the B C D part. So
a pretty simple change right here. I'm gonna show you there's a slightly different way to
formulate the same thing in a little bit, but
-anybody want to own up to having something that confuses them? [Inaudible] ask how you, like,
what you would set up to test it?
So [inaudible] one of
the, you know, the easiest thing to do here, and I have the code kind of actually sitting over
here just in case, right,
hoping you would
ask because right now I just have the most barebones sort of testing. It's like, yeah, what if I just,
you know, throw some strings at it and see what happens, right?
And so
the easiest strings to throw at it would be things like, well what happens if I give it the empty
string,
right? You know, so it takes some really simple cases to start because you want to see, well what happens
when, you know, you give it an empty input. Is it gonna blow up? And it's, like, the empty input,
right, immediately realizes there's no choices and it says, well, look, there's nothing to
print other than that empty string.
What if I give it a single character string?
Right? I get that string back. I'm like,
okay, gives me a little bit of inspiration that it made one recursive call, right, and then hit
the base case on the subsequent one.
Now I start doing better ones. A and B,
and I'm seeing A B B A. Okay, so I feel like, you know, I got this, so if I put a C in
the front,
and I put the B A behind,
then hopefully what I believe is that
it's gonna try, you know, C in the front, and then it's gonna permute A and B
behind it, and then similarly on down.
So some simple cases that I can see
verifying that it does produce, kind of, the input string as itself, and then it does the
back end rearrangement, leaving this in the front, and then it makes the next choice for what can
go in the front, and then the back end rearrangement. And kind of seeing the
pattern that matches my belief about how the code works, right,
helps me to feel good. What happens if I
put in
something that has double letters in it?
So I put A P P L E in there.
And all the way back at the beginning, right, I can
plot more of them, right, that grows quite
quickly right as we add more and more letters, right? Seeing the apple, appel,
and stuff like that.
There's a point where it starts picking the P to go in the front,
and the code as it's written, right, doesn't actually make it a combination for this P
and this P really being different.
So it goes through a whole sequence of
pull the second character to the front, and then permute the remaining four.
And then it says, and now pull the third character to the front and permute
the remaining four, which turns out to be exactly the same thing. So there should be
this whole sequence in the middle, right,
of the same Ps
repeated twice
because we haven't gone over a way to do anything about that, right?
So
-but it is reassuring to know that it did somehow didn't get, you know, confused by the idea of
there being two double letters. [Inaudible] if I do this -if I just say A
B A, right?
Something a little bit smaller to look at, right?
A in the front. A in the front goes permuted, B in the front, and then it ends up permuting
these two ways that ends up being exactly the same, and then I get a duplicate of those in
the front.
So right now, it doesn't know that there's anything to worry about in terms
of duplicates?
What's a really easy way to get rid of duplicates?
Don't think recursively, think -use a set.
Right? I could just stuff them in a set, right?
And then if it comes across the same one again it's like, yeah,
whatever. So it would still do the extra work of finding those down,
but would actually, like, I could print the set at the end having coalesced any of the duplicates.
To
actually change it in the code,
it's actually not that hard either.
The idea here is that
for all of the characters that remain, right,
and sometimes what I want to choose from is of the remaining characters
uniqued,
right? Pick one to move to the front.
So if there's three more Ps
that remain in rest,
I don't need to try each of those Ps individually in the front, right? They'll produce
the same result -pulling one and leaving the other two behind
is completely irrelevant.
So an easy way to actually stop it from even generating them,
is when looking at the character here is to make sure that it is -that it
doesn't duplicate anything else in the rest. And so
probably the easiest way to do that is to either pick the first of the Ps or the last
of the Ps, right, and to recur on and ignore the other ones.
So, for example, if right here I did a find on the rest
after I -do you see any more of these?
And if you do,
then skip it and just let those go. Or, you know,
do the first. Don't do the remaining ones. You can either look to the left of look to the
right and see if you see any more, and if so,
skip the,
you know, early or later ones depending on what your strategy is.
Any questions about permute here? [Inaudible].
So the [inaudible] can be just -look down here, right, it just looks like that, right?
This is a very common thing. You'll see this again, and again, and it tends to be that the
outer call, right, it tends to have this sort of
this, you know, solve this problem,
and then it turns out during the recursive calls you need to maintain some state
about where you are in the problem. You know, like, how many letters you moved, or
what permutation you've built so far, or where you are in the maze, or whatever it is you're
trying to solve.
And so typically that wrapper call is just gonna be setting up the initial call in a
way that has the initial form of that state
present
that the client to the function didn't need to know about. It's just our own housekeeping that we're
setting up.
Seems almost kind of silly to write down the function that has just line that just turns it
into, basically, it's just exchanging
-setting up the
other parameters.
I
am going to show you the other kind of master patter, and
then we're gonna go on to kind of use them to solve other problems.
This is the one that was already alluded to, this idea of a combinations. Instead
of actually producing all of the four character strings that involve
rearrangements of A B C D,
what if I were to [inaudible] in kind of the subgroups, or the way I could chose certain
characters out of that
initial input, and
potentially exclude some, potentially include some? So if I have A B C,
then the subsets of the subgroups of that
would be the single characters A B and C. The empty string A B and C itself the
full one, and then the combinations of two, A B, A C, and B C.
Now, in this case we're gonna say that order doesn't matter. We're not -whereas permutations was all
about order, I'm
gonna use -I'm gonna structure this one where I don't care. If it's A B or
B A I'm gonna consider it the same subset.
So I'm just interested in inclusion. Is A in or out? Is B in or out? Is C in or out?
And so the recursive strategy we're gonna take is exactly what I have just
kind of alluded to in my English description there,
is that I've got an input, A B C.
Each of those elements has either the opportunity of being in the subset or
not.
And I need to make that decision for everyone
-every single element, and then I need to kind of explore all the possible
combinations of that, right?
When A is in, what if B is out? When A is in, what if B is in?
So the recursion that I'm gonna use here
is that at each step of the way, I'm gonna separate one element from the
input,
and probably the easiest way to do that is just to kind of take the front
most element off the input
and sort of
separate it into this character by itself and then the remainder. Similarly, the way
I did with permute,
and then given that element I have
earmarked here, I can
try putting it in the current subset or not. I need to try both, so I'm gonna make
two recursive calls here,
one recursive call where I've added it in,
one recursive call where I haven't added it in. In both cases, right, I will have
removed it from the rest,
so what's being chosen from to complete that subset
always is a little bit smaller, a little bit easier.
So this is very, very much like the problem I described as the chose
problem. Trying to choose four people from a dorm to go to flicks was
picking Bob
and then -[inaudible] to Bob and not Bob, and then
saying, well, Bob could go, in which I need to pick three people to go with him,
or Bob could not go and I need to pick four people to go without Bob.
This is very much that same pattern. Two recursive calls. Identify one in or out.
The base case becomes when there's nothing left
to check out.
So I start with the input A B C -A
B C D let's say.
I look at that first element -I just need to pick one. Might as well pick the front one, it's the
easy one to get to.
I add it to the subset,
remove it from the input, and make a recursive call.
When that recursion completely terminates,
I get back to this call,
and I do the same thing again.
Remaining input is B C D again but now the subset that I've been building doesn't
include.
So inclusion exclusion
are the two things that I'm trying. So the
subset problem, right, very similar in structure to the way that I set
up permutations, right, as I'm gonna keep track of two strings as I'm working my way
down
the remainder in the rest, right, things that I haven't yet explored
so far is what characters I've chosen to place into the subset that I'm building.
If I get to the end where there's nothing left in the rest, so there's no
more choices to make,
then what I have in the subset is what I have in the subset, and I go ahead and print it.
In the case that there's still something to look at
I make these two calls,
one where I've appended it in, where I haven't, and then both cases, right, where I
have subtracted it off of the
rest by using the subster to
truncate that front character off.
So the way that
permute was making calls, right, was in a loop,
and so sometimes it's a little bit misleading. You look at it and you think there's
only one recursive call, but in fact it's in inside a loop, and so it's making,
potentially, end recursive calls where end is the length of
the input.
It gets a little bit shorter each time through but there's always, you know, however many
characters are in rest is how many recursive calls it makes.
The subsets code actually makes exactly two recursive calls at any given stage, in or out,
and then recurs on that and what is one remaining.
It also needs a wrapper
for the same exact reason that permutations did. It's
just that we are trying to
list the subsets of a particular string, in fact, there's some housekeeping that's going along
with it. We're just trying the subset so far is something we don't necessarily
want to put into the public interface in the way that somebody would have to
know what to pass to that to get the right thing. Anybody have
a question about this?
So given the way this code is written,
what is the first subset that is printed if I give it the input A B C D?
A B C D. Just like it was with permute, right? Everything went in.
What is the second one printed after that?
A B C, right? So I'm
gonna look at my little diagram with you
to help kind of trace this process of the recursive call, right, is that
the leftmost arm is the inclusion arm, the right arm is the exclusion arm.
At every level of the tree, right, we're looking at the next character of
the rest and deciding whether to go in or out,
the first call it makes is always in,
so at the beginning it says, I'm choosing about A. Is A in? Sure.
And then it gets back to the level of recursion. It says, okay, look at the first
thing of rest, that's B. Is B in? Sure. Goes down the right arm, right?
Is C in? Sure. Is D in? Sure. It gets to here and now we have nothing left, so we
have [inaudible] A B C D.
With the rest being empty, we go ahead and print it [inaudible] there's no more choices to
make. We've looked at every letter and decided whether it was in or out.
It will come back to here, and I'll say, okay, I've finished all the things I can make
with D in,
how about we try it with D out. And so then D out
gives us just the A B C.
After it's done everything it can do with
A B C in, it comes back to here and says, okay, well now do this arm,
and this will drop C off, and then try D in, D out.
And so it will go from the biggest sets to the smaller sets, not quite
monotonically though.
The very last set printed will be the empty set,
and that will be the one where it was excluded all the way down, which after it kind of tried
all these combinations of in out, in out, in out, it
eventually got to the out, out, out, out, out, out, out case which will give me the
empty set on that arm.
Again, if I reverse the calls, right, I'd still see all the same subsets in
the end. They just come out in a different order.
But it is worthwhile to model the recursion in your own head to have this
idea of understanding about how it goes deep, right? That
it always makes that recursive call and has to work its way all the way to the
base case and terminate that recursion before it will unfold
and revisit the second call that was made, and
then fully explore where it goes before it completes that whole sequence.
Anybody want to ask me a question about these guys? These are
just really, really important pieces of code, and so I'm trying to
make sure that I don't move past something that still feels a little bit
mystical or confusing to you because
everything I want to do for the rest of today
builds on this.
So now if there's something about either of these pieces of code
that would help you -yeah. What would
be the simplest way to do that?
So probably the simplest way, like, if you said, oh, I just really want it to be in alphabetical order,
would be to put them in a set, right, and then
have the set be the order for you. So you said
order doesn't matter? Oh, you
did care about how they got ordered. So, like, let's say you
didn't want B C D to equal C D B.
So in that case, right, you would be more likely to kind of add a permutation step into
it, right? So if B C D was not the same thing as A B C, right, it would be, like,
well
I'm gonna chose -so in this case, right,
it always -well the subsets will always be printed as kind of a subsequence. So -and let's
say if the input was the alphabet, just easy way
to describe it,
all of the subsets I'm choosing will always be in alphabetical order because I'm always choosing A in or not, B in
or not.
If I really wanted B Z to be distinct from Z B,
then really what I want to be doing at each step is picking the next character to go,
and not
always assuming the next one had to be the next one in sequence, so I would do more like a
permute kind of loop that's like pick the next one that goes, remove it from what
remains and recur,
and that I need that separate step we talked about of -and
in addition to kind of
picking, we also have to
leave open the opportunity that we didn't pick anything and we just kind of left the subject as is, right, so we
could [inaudible] or not. And
so permute always assumes we have to have picked everything. The subset code
would also allow for
some of them just being entirely skipped.
So we pick the next one, right, and then eventually
stopped picking.
[Inaudible] just in your wrapper function
then [inaudible] put a for loop or something like that, right? When you're through changing your string? Yeah, you can certainly do that, like in a permute from the outside too, right.
So there's often very, you know,
multiple different ways you can get it the same thing whether you want to put it in the recursion or
outside the recursion,
have the set help you do it or not,
that can get you the same result.
So let me try to
identify what's the same about these to try to kind of back away from it and
kind of
move just to see how these are more similar than they are different, right,
even though the code ends up kind of being -having some details in it
that -if you kind of look at it from far away these are both problems that are
about
choice.
That the recursive calls that we see have kind of a branching structure and a depth factor
that actually relates to the problem if you think about it in terms of decisions,
that in making a permutation your decision is what character goes next, right? In the
subset it's like, well, whether this character goes in or not
that the recursive tree that I was drawing that it shows all those calls,
the depths of it represents the number of choices you make. Each
recursive call makes a choice, right? A yes, no, or a next letter to go, and then recurs from
there. So I make, you know,
one of those calls, and then there's N minus 1 beneath it that represent
the further decisions I make that builds on that. And so, in the case of permutation, once I've
picked the, you
know, N minus 1
things to go, there's only one thing left, right? And so in some sense the tree is
N because I have to pick N things that go in the permutation and then I'm
done.
In the subsets, it's also N, and that's because for each of the characters I'm deciding
whether it's in or out. So I
looked at A and decided in or out. I looked at B and decided in or out. And I did that all the
way down.
That was the life of the input.
The branching
represents how many recursive calls were made
at each level of the recursion. In the case of subsets, it's always exactly two.
In, out, all the way down,
restarts at 1, branches to 2, goes to 4, goes to 8, 16, and so on.
In the permute case, right,
there are N calls at the beginning. I have N different letters to choose from, so
it's a very wide spread there, and that at that next level, it's N minus 1.
Still very wide. And N minus 2. And
so the overall tree has kind of an N times N minus 1 times N minus
2 all the way down to the bottom, which the factorial function
-which grows very, very quickly.
Even for small inputs, right, the number of permutations is enormous.
The number of subsets is to the end
in or out, right, all the way across.
Also, a very,
you know,
resource intensive problem to solve, not nearly as bad as permutation, but both of
them, even for small sizes of N, start to become pretty quickly intractable.
This is not the fault of recursion, right, these problems are not hard to solve because
we're solving them in the wrong way. It's because there are N factorial permutations. There are
[inaudible] different subsets,
right? Anything that's going to print to the N things, or N factorial things is going
to do N factorial work to do so. You can't avoid it.
There's a big amount of work to be done in there.
But what we're trying to look at here is this idea that those trees, right,
represent decisions.
There's some decisions that are made, you know, a decision is made at each level of recursion,
which then
is kind of a little bit closer
to having no more decisions to make. You have so many decisions to make, which is
the depth of the recursion. Once you've made all those decisions, you hit your base case
and you're done. The
tree being very wide and very deep makes for expensive exploration.
What we're gonna look at is a way that we can take the same structure of the
problem, one that fundamentally could be exhaustive, exhaustive meaning tried every
possible combination, every possible rearrangement and option,
and only explore some part of the tree.
So only look around in some region,
and as soon as we find something that's good enough.
So in the case, for example, of a search problem, it might be that we're searching
this space that could potentially cause us to look at every option,
but we're also willing to say if we make some decisions that turn out good enough,
that get us to our goal, or whatever it is we're looking for,
we won't have to keep working any farther. So I'm gonna show
you how we can take an exhaustive recursion problem and turn it into
what's called a recursive backtracker. So
there's
a lot of text on this slide but let me just tell you in English what we're trying to
get at.
That
the idea behind permutations or subsets is that at every level there's all
these choices and we're gonna try every single one of them.
Now imagine we were gonna make a little bit less a guarantee about that.
Let's design the function
to return some sort of state that's like I succeeded or I failed. Did
I find what I was looking for?
At each call, I still have the possibility of multiple calls of in out, or a choice
from what's there.
I'm gonna go ahead and make the choice,
make the recursive call,
and then catch the result from that recursive call, and see whether it
succeeded. Was that a good choice? Did that choice get me to where I wanted to be?
If it did,
then I'm done.
I won't try anything else. So I'll stop early,
quite going around the for loop, quit making other recursive calls,
and just immediately [inaudible] say I'm done.
If it didn't
-it came back with a failure, some sort of code that said it didn't get where I
want to do, then I'll try a different choice.
And, again, I'll be optimistic. It's a very optimistic way of doing stuff. It says
make a choice, assume it's a good one, and go with it.
Only when you learn it didn't work out
do you revisit that decision and back up and try again.
So let me show you the code. I think it's gonna make more sense, actually, if
I
do it in terms of looking at what the code looks like.
This is the pseudo code at which all recursive backtrackers at their heart
come down to this pattern.
So what I -I tried to be abstract [inaudible] so what does it mean to solve a
problem, and what's the configuration? That depends on the domain and the problem
we're trying to solve.
But the structure of them all looks the same in that sense that
if there are choices to be made -so the idea is that we cast the problem as a decision
problem.
There are a bunch of choices to be made.
Each [inaudible] will make one choice
and then attempt to recursively solve it. So
there's some available choices, in or out, or one of next, or where to place a
tile on a board, or whether to take a left or right turn and go straight in a
maze. Any of these things could be the choices here.
We make a choice,
we feel good about it, we commit to it,
and we say, well, if we can solve from here -so we kind of update our statement so we've made
that term, or,
you know, chosen that letter, whatever it is we're doing.
If that recursive call returned true
then we return true,
so we don't do any unwinding. We don't try all the other choices. We stop that for
loop early.
We say that worked. That was good enough.
If the solve came back with a negative result,
that causes us to unmake that choice,
and then we come back around here and we try another one.
Again, we're optimistic. Okay, left didn't work, go straight.
If straight doesn't work, okay, go right. If right didn't work and we don't have any
more choices, then we return false, and
this false is the one that then causes some earlier decision to get unmade
which allows us to revisit some earlier optimistic choice, undo it, and
try again.
The base case is hit when we run out of choices
where we've -whatever configuration we're at is, like, okay, we're at a dead end, or we're at
the goal, or we've
run out of letters to try. Whatever it is, right, that tells us, okay, we didn't
-there's nothing more to decide. Is this where we wanted to be?
Did it solve the problem?
And I'm being kind of very deliberate today about what does it mean [inaudible] update the configuration, or what does it
mean for it to be the goal state because for different problems it definitely means different
things. But the code for them all looks the same
kind of in
its skeletal form.
So let me take a piece of code and turn it into a recursive backtracker with you.
So I've got recursive permute up
here. So as it is, recursive permute tries every possible permutation, prints them all.
What I'm interested in is is
this sequence a letters an anagram. Meaning, it is -can be rearranged into
something that's an English word. Okay.
So what I'm gonna do is I'm gonna go in and edit it. The
first thing I'm gonna do is I'm gonna change it to where it's gonna return some
information.
That information's gonna be yes it works, no it didn't. Okay? Now I'm gonna do this.
I'm
gonna
add a parameter to this because I -in order to tell that it's a word I have to
have someplace to look it up. I'm gonna use the lexicon that actually we're using on this
assignment.
And so
when I get to the bottom
and I have no more choices, I've got some permutation I've assembled here in -so
far.
And I'm going to check and see if it's in the dictionary.
If the dictionary says that that's a word then
I'm gonna say this was good. That permutation was good.
You don't need to look at any more permutations. Otherwise I'll return false which will
say, well, this thing isn't a word. Why don't you try again?
I'm gonna
change the name of the function while I'm at it to be a little more descriptive, and we'll call it is anagram.
And then when I make the call here [inaudible]
third argument.
I'm not just gonna make the call and let it go away. I really want to know did that
work, so I'm gonna say, well, if
it's an anagram
then return true.
So if given the choice I made -I've got these letters X J Q P A B C,
right?
It'll pick a letter and it'll say, well if, you know, put that letter in the front
and then go for it. If you can make a word out of having made that
choice, out of what remains, then you're done. You don't need to try anything else. Otherwise
we'll come back around and make some of the further calls in that loop
to see if it worked out.
At the bottom, I also need
another failure case here,
and that comes when
the earlier choices, right -so I got, let's say somebody has given me X J,
and then it says, given X J, can you permute A and B to make a word? Well, it turns out
that
you can -you know this ahead of time. It doesn't have the same vision
you do. But it says X J? A B? There's just nothing you can do but it'll try them all
dutifully. Tried A in the front and then B behind, and then tried B in the front and A behind it, and
after it says that, it says, you know what, okay, that just isn't working, right?
It must be some
earlier decision that was really at fault.
This returned false is going to cause
the, you
know, sort of stacked up previous anagram calls to say, oh yeah, that
choice of X for the first letter was really
questionable. So imagine I've had, like, E X, you know,
T I. I'm trying to
spell the word exit -is a possibility of it. That once I have that X in the
front it turns out nothing is going to work out, but it's gonna go through and try X
E I T, X E T I, and so on.
Well, after all those things have been tried it says, you know what, X in the front wasn't it,
right? Let's try again with I in the front. Well after it does that it won't get anywhere either.
Eventually it'll try E in the front
and then it won't have to try anything else after that because that will eventually
work out.
So if I put this guy in like that,
and I
build myself a lexicon, and then
I change this to
anagram word. I
can't spell. I'd better
pass my lexicon because I'm gonna need that to
do my word lookups.
[Inaudible]. And down here.
Whoops.
Okay. I
think
that looks like it's okay. Well, no
-finish this thing off here.
And so if I type in, you know, a word that I know is a word to begin
with,
like
boat, I happen to know the way the permutations work [inaudible] try that right away and find
that.
What if I get it toab, you know, which is a rearrangement of that, it eventually did find them.
What if I give it something like this,
which there's just no way you can get that in there. So it seems to [inaudible] it's
not telling us where the word is. I can actually go and change it.
Maybe that'd be a nice thing to say. Why don't I print the word
when it finds it? If
lex dot contains
-words so far
-then print it. That
way I can find out what word it thinks it made out of it. So if I
type toab -now
look at that, bota. Who would know? That dictionary's full of some really ridiculous
words.
Now I'll get back with exit. Let's type some other words.
Query. So it's finding some
words, and then if I give it some word that I know is just nonsense
it won't print anything
[inaudible] false.
And so in this case, what it's doing is its come to a partial exploration, right,
of the permutation tree
based on
this notion of being able to stop early on success. So in the case of this one, right,
even six nonsense characters, it really did do the full permutation, in this case,
the six factorial permutations, and discover that none of them worked.
But in the case of exit or the
boat that,
you know, early in the process it may have kind of made a decision, okay so [inaudible]
in this case it will try all the permutations with Q in the front,
right?
Which means, okay, we'll go with it, and then it'll do them in order to start with, but it'll
start kind of rearranging and jumbling them up, and eventually, right,
it will find something that did work with putting in the front, and it will never unmake that
decision about Q. It will just sort of have -made that decision early,
committed to it, and worked out, and then it covers a whole space of the tree that never got
explored of R in front, and Y in the front, and E in the front
because it had a notion of
what is a satisfactory outcome. So the base case that it finally got to in
this case met the standard for being a word was all it wanted to find, so it just
had to work through the base cases
until it found one,
and potentially that could be very few of them relative the huge space. All right.
I have this code
actually on this slide. So it's
permute, and that is turning into is anagram. And so, in blue, trying to highlight
the things that changed in the process, right, that
the structure of kind of how it's exploring, and making the recursive calls is exactly
the same.
But what we're using now is some return information from the function to
tell us how the progress went,
and then
having our base case return some sense of did we get where we wanted to be,
and then when we make the recursive call, if it did succeed, right,
we immediately return true and unwind out of the recursion,
doing no further exploration,
and in the case where all of our choices
gave us no success, right, we will return the call that says, well that was unworkable how we got
to where we were.
So this is the transformation that
you want to feel like you could actually sort of apply again and again, taking
something that was exhaustive, and looked at a whole space,
and then had -change it into a form where it's like, okay, well I wanted to stop
early when I get to something that's good enough.
A lot of problems, right, that are recursive backtrackers just end up being
procedural code
that got turned into this
based on a goal that you wanted to get to being one of the possibilities of the
exploration.
Anybody have any questions of what we got there? Okay.
I'm gonna show you some more
just because they are
-there are a million problems in this space, and the more of them you see, I
think, the more the patterns will start to emerge.
Each of these, right, we're gonna think of as decision problems, right, that we have some number
of decisions to make,
and we're gonna try to
make a decision in each recursive call
knowing that that gives us fewer decisions that we have to make in the
smaller form of the sub problem that we've built that way,
and then the decisions that we have open
to us, the options there
represent the different recursive calls we can make. Maybe it's a for loop, or
maybe a list of the explicit alternatives that we have
that will be open to us in any particular call.
This is a CS kind of classic problem. It's one that, you know, it doesn't seem like
it has a lot of utility but it's still interesting to think about, which is if
you have an eight by eight chessboard, which is the standard chessboard size,
and you had eight queen pieces,
could you place those eight queens on the board
in such a way that no queen is threatened by any other? The queen is
the most powerful
player on the board, right, can move
any number of spaces horizontally, vertically, or diagonally on any
straight line basically,
and so it does seem like, you know, that there's a lot of contention on the
board to get them all in there in such a way that they can't
go after each other.
And so if we think of this as a decision problem,
each call's gonna make one decision and recur on the rest. The decisions we have to
make are
we need to place, you know, eight queens let's say, if the board is an eight by eight board.
So at each call we could place one queen, leaving us with M minus 1 to
go.
The choices for that queen might be that one way to kind of
keep our problem
-just to manage the logistics of it is to say, well, we know that there's going to be a
queen in each column,
right,
it certainly can't be that there's two in one column. So
we can just do the problem column by column and say, well, the first thing we'll do is place
a queen in the leftmost column.
The next call will make a queen
-place a queen in the column to the right of that, and then so on. So we'll work our way
across the board from left to right,
and then the choices for that queen
will be any of the [inaudible]
and some of those actually are -we may be able to easily eliminate as
possibilities. So, for example, once this queen is down here in the bottommost row, and
we move on to this next column, there's no reason to even try placing the queen
right next to it because we can see that that immediately threatens.
So what we'll try is, is there a spot in this column that
works given the previous decisions I've made,
and if so, make that decision and move on.
And only if we learned that that decision, right,
that we just made optimistically isn't successful will we back up and try again.
So let me do a little demo with you.
Kind of shows this
doing its job.
Okay.
So [inaudible] I'm gonna do it as I said, kind of column by column.
[Inaudible] is that I'm placing the queen in the leftmost column to begin, and the question
mark here says this is a spot under consideration. I look at the
configuration I'm in,
and I say, is this a plausible place to put the queen?
And there's no reason not to,
so I go ahead and let the queen sit there.
Okay, so now I'm going to make my second recursive call. I say I've placed one queen, now there's three
more queens to go.
Why don't we go ahead and place the queens that remain to the right of this. And so
the next recursive call comes in and says, if you can place the queens given the
decision I've already made, then tell me yes, and then I'll know all is good.
So it looks at the bottommost row, and it says, oh, no, that won't work,
right? There's a queen right there.
It looks at the next one and then sees the diagonal attack. Okay. Moves up to
here and says, okay, that's good.
That'll work,
right? Looks at all of them and it's okay.
So now it says, okay, well I've made two decision. There's just two to go. I'm
feeling good about it. Go ahead and make the recursive call.
The third call comes in, looks at that row, not good,
looks at that row, not good,
looks at that row, not good, looks at that row, not good. Now this one -there weren't any
options at all that were viable.
We got here,
and given the earlier decisions, and so the idea is that, given our optimism, right, we
sort of made the calls and just sort of moved on. And now we've got in the situation where we
have tried all the possibilities in this third recursive call and there was
no way to make progress. It's gonna hit the return false at the bottom of the
backtracking that says,
you know what, there was some earlier problem.
There was no way I could have solved it given the two choices -or, you know, whatever
-we don't even know what choices were made, but there were some previous choices made, and
given the state that was passed to this call,
there's no way to solve it from here.
And so this is gonna trigger the backtracking. So
that backtracking is coming back to an earlier decision that you made and unmaking
it.
It's a return false coming out of that third call that then causes the second call to
try again.
And it goes up and it says okay, well where did I leave off? I tried the first couple of ones.
Okay, let's try moving it up a notch and see how that goes.
Then, again,
optimistic, makes the call and goes for it.
Can't do this one. That looks good.
And now we're on our way to placing the last queen, feeling really comfortable and
confidant,
but
discovering quickly,
right, that there was no possible. So it turns out this configuration with these three
queens, not solvable. Something must be wrong.
Back up to the most immediate decision. She knows it doesn't unmake, you know,
earlier decisions until it really has been proven that that can't work, so
at this point it says, okay, well let's try finding
something else in this
column.
No go.
That says, okay, well that one failed so it must be that I made the wrong decision in
the second column. Well, it turns out the second column -that was the last choice
it had. So in fact it really was my first decision
that got us off to the wrong foot.
And now, having tried everything that there was possible, given the queen in the
lower left in realizing none of them worked out, it comes back and says, okay, let's
try again, and at this point it actually will go fairly quickly.
Making that initial first decision
was
the magic that
got it solved. And
then we have a complete solution to the queens.
We put it onto eight,
and let it go.
You can see it kind of checking the board, backing up, and you notice that it
made that lower left decision kind of in -it's sticking to it, and so the idea is
that it always backs up to the most recent decision point
when it fails,
and only after kind of that one has kind of tried all its options will it actually
back up and consider a previous decision as being unworthy
and revisiting it.
In this case that first decision did work out,
the queen being in the lower left.
It turns out there were -you know, you saw the second one had to kind of slowly get
inched up in the second row. Right? It wasn't gonna work with the third row. It tried
that for a while. Tried the fourth row for a while.
All the possibilities after that, but eventually it was that fifth row
that then kind of gave it the breathing room to get those other queens out there.
But it did not end up trying, for example, all the other positions for the queen in
the first row, so it actually -it really looked at a much more constrained part of the entire
search tree than
an exhaustive recursion
of the whole thing would have done.
The code for that ?whoops
-looks something like this.
And
one of the things that I'll strongly encourage you to do when you're writing
a recursive backtracking routine,
something I learned from Stuart Regis, who long ago was my mentor,
was the idea that
when -trying to make this code look as simple as possible, that one of the things
you want to do is try to move away the details of the problem. For example,
like, is safe
-given the current placement of queens, and the row you're trying, and the column you're at,
trying to decide that there's not some existing conflict on the board with the
queen already being threatened by an existing queen just involves us
kind of traipsing across the grid and looking at different things.
But putting in its own helper function makes this code much easier to read, right?
Similarly, placing the queen in the board, removing the queen from the board,
there are things they need to do. Go up to state and draw some things on the
graphical display.
Put all that code somewhere else so you don't have to look at it, and then this
algorithm can be very easy to read. It's like for all of the row. So given
the column we're trying to place a queen in, we've got this grid
of boolean that shows where the queens are so far,
that for all of the rows across the board, if,
right, it's safe to place a queen in that row and this column, then place the
queen and see if you can solve
starting from the column to the right, given this new update to the board. If it
worked out, great, nothing more we need to do. Otherwise we need to take back that
queen, unmake that decision,
and try again.
Try a higher row. Try a higher row, right.
Again, assume it's gonna work out. If it does, great. If it doesn't, unmake it, try
it again. If we tried all the rows that were open to us,
and we never got to this case where this returned true, then we return false, which
causes some
previous one -we're backing up to a column behind it. So if we were currently trying to
put a queen in column two,
and we end up returning false, it's gonna cause column one to unmake a decision
and move the queen up a little bit higher.
If all of the options for column one fail, it'll back up to column zero.
The base case here at the end, is if we ever get to where
the column is past the number of columns on the board, then that means we placed a queen
all the way across the board and
we're in success land. So all
this code kind of looks the same kind of standing back from it, right, it's
like,
for each choice, if you can make that choice, make it.
If you solved it from here, great, otherwise, unmake that choice.
Here's my return false when I ran out of options. There's my base case -it says
if I have gotten to where there's no more decisions to make, I've placed all the
queens,
I've chosen all the letters, whatever, did I -am I where I wanted to be? There's no
some sort of true or false analysis that comes out there about
being in the right state. How do you feel
about that? You guys look
tired today, and
I didn't even give you an assignment due today, so this can't be my fault,
right?
I got a couple more examples, and I'm probably actually just gonna go ahead and try to spend some time on
them on Monday because I really don't want to -I
want
to
give you a little bit more practice though. So we'll see. We'll see. I'll do at
least one or two more of them on Monday before we start talking about pointers and linked lists, and so
I will see you then. But having a good weekend. Come and hang out in Turbine with me.