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

Groups > comp.programming > #6188 > unrolled thread

Rotation

Back to article view | Back to comp.programming

Contents

  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

#6188 — Rotation

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 

[toc] | [next] | [standalone]

#6195

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.

[toc] | [prev] | [next] | [standalone]

#6197

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

[toc] | [prev] | [next] | [standalone]

#6198

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

[toc] | [prev] | [next] | [standalone]

#6200

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

[toc] | [prev] | [next] | [standalone]

#6201

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

[toc] | [prev] | [next] | [standalone]

#6202

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.

[toc] | [prev] | [next] | [standalone]

#6203

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

[toc] | [prev] | [next] | [standalone]

#6199

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++;
}

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web