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

Groups > comp.programming > #6199

Re: Rotation

Show all headers | View raw

On Mon, 4 Jan 2016 09:25:50 -0800 (PST)
Paul <pepstein5@gmail.com> 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? 
> 
> Thank You 
> 
> Paul 
Well if this is not in place rather outputs to different list than it
is easy to understand.

next = middle;
while(next != last) {
	*out++=*next++;
}
next = first;
while(next != middle) {
	*out++=*next++;
}

Back to comp.programming | Previous | Next — Previous 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