[Tutor] Re: rotating a list [Programmer Pearls]

[Danny Yoo]

> >>No that is NOT the problem. That is an alternative algorithm. I explained
> >>the problem in my post.
> >
> >As far as I can tell, that's a matter of taste: the algorithm is
> >exactly the same and the result is the same: he uses the default value
> >of n=1 in this case to test his rotation which is just fine. One can
> >either increment n in the loop or reassign x every time. Personally, I
> >find reassigning more intuitive and I pretty much ignored the optional
> >n parameter. Could you explain why incrementing n is a superior
> >solution?
>
> I guess I overreacted in my reply. I did see what you saw first, then
> when I tested the code and saw the missing parameter I assumed the OP
> meant to provide it. Sorry for the reaction.

Hi Bob,

No problem; it just sounded a little confrontational at first.  Glad it's
cleared up now.

By the way, this subject about List Rotation is one that Jon Bentley talks
about in his excellent book, "Programming Pearls":

    http://www.cs.bell-labs.com/cm/cs/pearls/index.html

as Column 2.  I really like his handwavy analogy to doing the problem.
Unfortunately, Bentley only gives a sketch of Column 2 on his web site:

    http://www.cs.bell-labs.com/cm/cs/pearls/sketch02.html
    http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf

but I guess that makes sense, as it's an incentive for people to buy the
book.  Everyone, go visit your local bookstore sometime and read Column 2:
it's good!  *grin*


Anyway, for people who are interested: here's an implementation of the
handwavy example he describes:

###
>>> def reverse(L, a, b):
...     """Mutates a list L by reversing all the elements in L between
...        indices a and b, inclusive."""
...     while a < b:
...         L[a], L[b] = L[b], L[a]
...         a = a + 1
...         b = b - 1
...
>>> def rotate(L, n=1):
...     """Mutates list L by rotating it in a handwavy way."""
...     reverse(L, 0, n-1)
...     reverse(L, n, len(L) - 1)
...     reverse(L, 0, len(L) - 1)
...
>>> numbers = range(10)
>>> numbers
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> reverse(numbers, 0, 9)
>>> numbers
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>>
>>>
>>> rotate(numbers)
>>> numbers
[8, 7, 6, 5, 4, 3, 2, 1, 0, 9]
>>> rotate(numbers, 2)
>>> numbers
[6, 5, 4, 3, 2, 1, 0, 9, 8, 7]
###


Hope this helps!