Re: Fast pancake flipping

From: Peter (shaggy_at_australis.net.STOP.SPAM)
Date: 02/22/04

  • Next message: CBFalconer: "Re: Test-Driven Development (was Re: Career? What languages to learn?)" 
    Date: Sun, 22 Feb 2004 07:42:28 GMT

    Groovy hepcat Roger Willcocks was jivin' on Wed, 18 Feb 2004 20:46:55
    -0000 in comp.programming.
    Re: Fast pancake flipping's a cool scene! Dig it!

    >"Alf P. Steinbach" <alfps@start.no> wrote in message
    >news:40336a1f.620322015@news.individual.net...
    >> 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.
    >
    >But when there are multiple reversals you need a flag per element, since
    >each element could be subject to a different combination of flips, making
    >the flip operation O(F) where F is the number of elements being flipped.

      There is a way around this problem. Instead of a direction flag, put
    a reversal flag in each element (as long as "element" means a double
    linked list node or something, not an array element). When flipping a
    subset of the list, all you have to do is unlink the first and last
    elements (or nodes), re-link them in reverse, and flip the reversal
    flag in the element at the start and end of the subset. Then, when
    traversing the list, start by following the "next" links. When you
    encounter a reversal flag that is set, you follow the "prev" links
    instead. When you encounter another, you again follow "next" links.
    And so on.
      Or something like that. :)

    >You can also use something akin to a doubly linked list, where, when walking
    >the list,you infer which is the previous and which is the next pointer by
    >ignoring the one which points 'back' to the already visited neighbour. That

      That's another way. :)

    >way only the head and Nth element's pointers and neighbours need to be
    >updated during a flip. The problem is finding the Nth element in the first
    >place.
    >Personally I find an O(1) flipping solution unlikely since it would suggest
    >that having located the Nth element of an already flipped list in constant
    >time, the list can also be rearranged in constant time, while still allowing
    >O(1) location for the next iteration.

      Perhaps an array of pointers to the nodes could be kept for this
    purpose, and updated when traversing the list outside the flipping
    routine, between flips. This assumes, of course, that the list will be
    traversed outside the flipping routine, between flips. Traversing the
    list (for example, to print the values of the nodes) would be a O(n)
    operation anyhow, so why not embed another operation that would
    otherwise be a O(n) operation itself? 

    -- 
Dig the even newer still, yet more improved, sig!
http://alphalink.com.au/~phaywood/
"Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
I know it's not "technically correct" English; but since when was rock & roll "technically correct"?
  • Next message: CBFalconer: "Re: Test-Driven Development (was Re: Career? What languages to learn?)"
    Loading