Re: Fast pancake flipping

From: Richard Heathfield (invalid_at_address.co.uk.invalid)
Date: 02/19/04 

Date: Thu, 19 Feb 2004 06:33:27 +0000

Alf P. Steinbach wrote:

> On Wed, 18 Feb 2004 12:42:29 +0000, Richard Heathfield
> <invalid@address.co.uk.invalid> wrote:
>
>>James Dow Allen wrote:
>>
>><snip>
>>
>>> Here I don't ask you to solve the Pancake Flipping Problem; just
>>> to write a subroutine that will perform a specified flip in constant
>>> time independent of sequence or prefix length. Define your own data
>>> structure and function interface. After the flip, the data structure
>>> must still be in a form that allows further constant-time flips
>>> by the same routine.
>>
>>Assuming there is no upper bound on N (the sequence length), this problem
>>is insoluble, since swapping takes time, making the operation inherently
>>O(N).
>>
>>Am I missing something?
>
> You can reverse an entire sequence by inverting a boolean flag.
>
> You can reverse a prefix of N elements of a sequence by storing the number
> N somewhere, associated with the sequence, and adjusting indexing
> operations as
>
> ElementType& operator[] ( size_t i )
> {
> return (i < N? myElements[N-i-1] : myElements[i]);
> }

Assuming this works (which I didn't check), it only pushes the O(N) issue
sideways, instead of dealing with it during the flip. It doesn't
/eliminate/ the O(N) issue. I don't consider that to be a satisfactory
solution. 

-- 
Richard Heathfield : binary@eton.powernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

Relevant Pages

  • Re: Reverse order numbered list
    ... The challenge is to create such a sequence as my ... Brotha Iz ... Johnny Love Jazz ... Is there a simple method to display a numbered list in reverse ...
    (microsoft.public.word.numbering)
  • What about an EXPLICIT naming scheme for built-ins?
    ... can be used in expressions, as it returns a copy of the sequence, sorted. ... reverse() works in-place. ... The past tense of sort() indicates that a copy of the sequence is returned. ...
    (comp.lang.python)
  • Re: Reverse order numbered list
    ... The following is a far superior macro to ... Dim i As Long, Numrange As Range ... already have a list that he needed to number in reverse. ... set up the fields and then type the sequence. ...
    (microsoft.public.word.numbering)
  • Re: Fast pancake flipping
    ... >> problem is insoluble, since swapping takes time, making the operation ... > You can reverse an entire sequence by inverting a boolean flag. ... Look Ma, Opancake flips! ...
    (comp.programming)
  • Re: Cohens paper on byte order
    ... > you changed from a bit sequence to what appears to be ... an array of unsigned char to represent a bit array, ... in the reverse order instead? ... But the user input IS at the beginning a bit array ...
    (sci.crypt)