Asp Forum - Rotation - comp.programming

Paul

1/4/2016 5:26:00 PM

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/algorit...

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

8 Answers

David Brown

1/4/2016 10:51:00 PM

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/algorit...
>
> 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.

Bartc

1/5/2016 1:24:00 AM

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/algorit...
>
> 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

Kaz Kylheku

1/5/2016 4:59:00 AM

On 2016-01-05, BartC <bc@freeuk.com> wrote:
> 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/algorit...
>>
>> 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.
>
> 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

Lol, blub languages.

$ ./txr
This is the TXR Lisp interactive listener of TXR 129.
Use the :quit command or type Ctrl-D on empty line to exit.
1> (defparm a (range 0 9))
a
2> (defparm b (range 0 9))
b
3> a
(0 1 2 3 4 5 6 7 8 9)
4> b
(0 1 2 3 4 5 6 7 8 9)
5> (rotate [a 0..8] [a 8..:])
(0 1 2 3 4 5 6 7)
6> (rotate [b 0..2] [b 2..:])
(0 1)
7> a
(8 9 0 1 2 3 4 5 6 7)
8> b
(2 3 4 5 6 7 8 9 0 1)

Melzzzzz

1/5/2016 8:13:00 AM

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/algorit...
>
> 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++;
}

Bartc

1/5/2016 12:23:00 PM

On 05/01/2016 04:59, Kaz Kylheku wrote:
> On 2016-01-05, BartC <bc@freeuk.com> wrote:
>> On 04/01/2016 17:25, Paul wrote:

>>> I can verify that this code works for special cases but it's not
>>> intuitively clear that it should always work.

>> 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
>
> Lol, blub languages.
>
> $ ./txr
> This is the TXR Lisp interactive listener of TXR 129.
> Use the :quit command or type Ctrl-D on empty line to exit.
> 1> (defparm a (range 0 9))
> a
> 2> (defparm b (range 0 9))
> b
> 3> a
> (0 1 2 3 4 5 6 7 8 9)
> 4> b
> (0 1 2 3 4 5 6 7 8 9)
> 5> (rotate [a 0..8] [a 8..:])
> (0 1 2 3 4 5 6 7)
> 6> (rotate [b 0..2] [b 2..:])
> (0 1)
> 7> a
> (8 9 0 1 2 3 4 5 6 7)
> 8> b
> (2 3 4 5 6 7 8 9 0 1)

How does this relate to the problem of verifying the original C++ code?

Is it any easier to understand? It seems you are not actually
implementing a 'rotate' function function at all (AFAICS), but simply
using some built-on operator.

Then of course it becomes very easy! Any language can 'implement' rotate
as something like:

rotate_inplace(a,shiftcount)

because the work has already been done. But the same 'blub' language as
above can also define the rotation like this:

proc rotate_left(&a,count)=
a:=right(a,-count) concat left(a,count)
end

(But it requires extra workspace compared with the plain code above.)

--
Bartc

Bartc

1/5/2016 12:56:00 PM

On 05/01/2016 04:59, Kaz Kylheku wrote:

> $ ./txr
> This is the TXR Lisp interactive listener of TXR 129.
> Use the :quit command or type Ctrl-D on empty line to exit.

That's interesting. I got reprimanded by Richard Heathfield in c.l.c
last year for saying that you type Ctrl-D at the 'start' of a line. He
said that as the line doesn't yet exist, you can't have the start of it.

I wonder if talking about an 'empty' line is any different? He said
Ctrl-D is something you type /after/ the previous line is completed.

(Anyway I'm now apparently in his killfile because of that disagreement.)

--
Bartc

Kaz Kylheku

1/5/2016 2:37:00 PM

On 2016-01-05, BartC <bc@freeuk.com> wrote:
> On 05/01/2016 04:59, Kaz Kylheku wrote:
>
>> $ ./txr
>> This is the TXR Lisp interactive listener of TXR 129.
>> Use the :quit command or type Ctrl-D on empty line to exit.
>
> That's interesting. I got reprimanded by Richard Heathfield in c.l.c
> last year for saying that you type Ctrl-D at the 'start' of a line. He
> said that as the line doesn't yet exist, you can't have the start of it.
>
> I wonder if talking about an 'empty' line is any different? He said
> Ctrl-D is something you type /after/ the previous line is completed.
>
> (Anyway I'm now apparently in his killfile because of that disagreement.)

That was likely in relation to the Unix TTY EOF signal. I seem to recall
the discussion. My Ctrl-D is different in that usually it is
the visual edit key for "erase character under the cursor, and shift the
remaining ones left". The exit semantics of Ctrl-D (which is always
Ctrl-D regardless of the EOF character configured in the TTY) only
applies when the edit buffer is completely empty, for the sake of
complying with a common convention.

(I should put in a check to suppress the exit semantics if the last
command was a successfully executed deletion via Ctrl-D, so that if the
user uses keyboard repeat to delete everything in the current line, it
won't exit.)

In the case of canonical Unix TTY input, Ctrl-D (or whatever character
is configured for that role) just means "cause the read system call to
bail immediately, returning whatever characters have been accumulated
into the caller's buffer already".

If this occurs when no characters have been accumulated, then read
returns 0, which looks like end-of-file. Indeed, no line of
input is obtained, since no input is obtained at all.
That doesn't mean that there never existed a line at all! The TTY user
can edit the input line, then backspace over it and issue Ctrl-D. The
process doesn't know about the line, but the line certainly existed in
the operating system kernel.

If Ctrl-D is used in the middle of a line of input, then the
process is resumed with exactly that input coming out of read,
without any terminating newline. This is useful from time to time, like
in interactively testing how some program reacts to the last line of
input not being properly terminated.

Bartc

1/5/2016 6:49:00 PM

On 05/01/2016 14:37, Kaz Kylheku wrote:
> On 2016-01-05, BartC <bc@freeuk.com> wrote:
>> On 05/01/2016 04:59, Kaz Kylheku wrote:
>>

>>> Use the :quit command or type Ctrl-D on empty line to exit.
>>
>> That's interesting. I got reprimanded by Richard Heathfield in c.l.c
>> last year for saying that you type Ctrl-D at the 'start' of a line. He
>> said that as the line doesn't yet exist, you can't have the start of it.
>>
>> I wonder if talking about an 'empty' line is any different? He said
>> Ctrl-D is something you type /after/ the previous line is completed.

> In the case of canonical Unix TTY input, Ctrl-D (or whatever character
> is configured for that role) just means "cause the read system call to
> bail immediately, returning whatever characters have been accumulated
> into the caller's buffer already".
>
> If this occurs when no characters have been accumulated, then read
> returns 0, which looks like end-of-file. Indeed, no line of
> input is obtained, since no input is obtained at all.
> That doesn't mean that there never existed a line at all! The TTY user
> can edit the input line, then backspace over it and issue Ctrl-D.

Yes. Or a possible new line existed in the mind of the user, who then
decides to type Ctrl-D first.

(A bit like changing your mind about going for a drive at the start of a
proposed trip. The decision is determined by something other than the
simple fact of finishing the previous trip or completing the previous
line. And there might not have been a previous line!)

--
Bartc

comp.programming

Rotation

Paul

David Brown

Bartc

Kaz Kylheku

Melzzzzz

Bartc

Bartc

Kaz Kylheku

Bartc

x Login to ForumsZone