Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.programming > #6199
| Path | csiph.com!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!feeder.erje.net!1.eu.feeder.erje.net!news.albasani.net!.POSTED!not-for-mail |
|---|---|
| From | Melzzzzz <mel@zzzzz.com> |
| Newsgroups | comp.programming |
| Subject | Re: Rotation |
| Date | Tue, 5 Jan 2016 09:13:13 +0100 |
| Organization | albasani.net |
| Lines | 52 |
| Message-ID | <20160105091313.2ff01847@maxa-pc> (permalink) |
| References | <f8f1edff-9175-4210-8877-fdd0ffa4f42c@googlegroups.com> |
| Mime-Version | 1.0 |
| Content-Type | text/plain; charset=US-ASCII |
| Content-Transfer-Encoding | 7bit |
| X-Trace | news.albasani.net lSVpPQZpt4z+6x59uRzkGdyjOk2mU8u4WggqWMHo+uhhNrSsYVks38SqRJ6Fc2iyXDoBtdhSbS6Ze5w+7tKbJg== |
| NNTP-Posting-Date | Tue, 5 Jan 2016 08:13:13 +0000 (UTC) |
| Injection-Info | news.albasani.net; logging-data="xGBQ6AvegXVRSaZifhY5/yPvYKC4qe2NmKMTxDIpHpYeBSBN0eeafDqdIHAEPUWOjUWVr4ONkAXD5BiFcmh6nhJrG7wU1NP7swjyiSHqjzEGwvpUYZ910BEYKArYEGvd"; mail-complaints-to="abuse@albasani.net" |
| X-Newsreader | Claws Mail 3.13.1 (GTK+ 2.24.29; x86_64-unknown-linux-gnu) |
| Cancel-Lock | sha1:GFsjZ8ZegS0U2IVTgI426+9MpnE= |
| Xref | csiph.com comp.programming:6199 |
Show key headers only | 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
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