Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #6195

Re: Rotation

Show all headers | View raw

On 04/01/16 18:25, Paul wrote:
> Suppose we want to rotate the list of numbers [1, 2, 3, 4, ..., 10]
> so  that it begins with a 4 and we end up with [4,...10, 1, 2, 3].
>
> I was looking at the standard-library c++ way to do this from
> http://www.cplusplus.com/reference/algorithm/rotate/
>
> There we get (as an example) the code below. To rotate as above,
> middle would be the pointer to 4 which is indexed 3 in c++ which begins
> counting at zero.
>
> template <class ForwardIterator>
>    void rotate (ForwardIterator first, ForwardIterator middle,
>                 ForwardIterator last)
> {
>    ForwardIterator next = middle;
>    while (first!=next)
>    {
>      swap (*first++,*next++);
>      if (next==last) next=middle;
>      else if (first==middle) middle=next;
>    }
> }
>
>
> I can verify that this code works for special cases but it's not
> intuitively clear that it should always work. Basically, I don't
> understand why it should work as an algorithm for rotation, although I
> can verify it.
>
> What is a good intuitive way of seeing that this algorithm rotates a
> list, and what is a good way (or text) for improving intuition about
> thinking about these things so that I can come up with such algorithms
> by myself?
>

I think the easiest way to understand this would be to get a piece of 
paper divided into columns - "first", "middle", "last", "next", "do the 
if bit", "do the else if bit", and then the ten entries in your list. 
Just step through the code manually, filling in each row.  It won't take 
long, and you will see exactly how it works.

Good old fashioned pencil-and-paper tracing is underrated these days.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Rotation Paul <pepstein5@gmail.com> - 2016-01-04 09:25 -0800
  Re: Rotation David Brown <david.brown@hesbynett.no> - 2016-01-04 23:51 +0100
  Re: Rotation BartC <bc@freeuk.com> - 2016-01-05 01:24 +0000
    Re: Rotation Kaz Kylheku <kaz@kylheku.com> - 2016-01-05 04:59 +0000
      Re: Rotation BartC <bc@freeuk.com> - 2016-01-05 12:22 +0000
      Re: Rotation BartC <bc@freeuk.com> - 2016-01-05 12:55 +0000
        Re: Rotation Kaz Kylheku <kaz@kylheku.com> - 2016-01-05 14:37 +0000
          Re: Rotation BartC <bc@freeuk.com> - 2016-01-05 18:48 +0000
  Re: Rotation Melzzzzz <mel@zzzzz.com> - 2016-01-05 09:13 +0100

csiph-web