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

Groups > comp.programming > #6197

Re: Rotation

Show all headers | View raw

On 04/01/2016 17: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.

It's easy enough to test. I'm not familiar with C++ so I tried this 
somewhat different language, doing an in-place left-rotation of the 
caller's data:

proc rotate(&a,middle)=
     first := a.lwb
     last := a.upb+1
     next := middle

     while first <> next do
         swap(a[first++], a[next++])
         if next = last then
             next := middle
         elsif first = middle then
             middle := next
         fi
     od
end

(Apparently, 'last' in the C++ code points to one past the last element.)

With a suitable test program to drive it, you pass it your 10-element 
array and test with middle = 1 to 10 (if 1-based). Then you try smaller 
sizes, such as arrays of sizes 0, 1, 2 and 3 which could be troublesome. 
If those are fine, I can't see any reason it can't work for any size of 
list.

> 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 couldn't see how it worked, but I'm happy to use the algorithm 
provided I'm confident it does work. I wouldn't be able to come up with 
something that rotated the other way though, not as efficiently as this 
anyway.

(Maybe I can reverse the list, rotate left, then reverse again in order 
to rotate right. Or I can do an easier single position shift and call it 
multiple times. Or go high-level and do something like:

   right(a,-middle) & left(a,middle)

But this isn't in-place and not that efficient.)

-- 
Bartc

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