| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 1973.1 | | EVMS::HALLYB | Fish have no concept of fire | Thu May 25 1995 10:46 | 19 |
| If I understand this right it is clear that 2n is an upper bound on
the number of operations. For any string of length n you can move the
largest element to the end in 2 operations and thus reduce the problem
to sorting a string of length n-1.
E.g., given the string 27164 you bring the 7 to the front: 72164 and
then reverse the whole string: 46127. Now you only need sort 4612 and
by the same token that takes 2 steps to yield 2146, and so on.
You can save a step or two in the above anytime you have two position-
adjacent elements that are also order-adjacent. E.g., 14762 becomes
67412 then 76412 then 21467, ordering two elements in 3 steps. Had it
been 14672 you do even better: 76412, 21467 -- only 2 steps.
It certainly seems difficult to come up with a counterexample;
"adjacancies" keep cropping up. It would seem to me that coming up with
an algorithm for minimizing reversals would involve maximizing adjacencies.
John
|
| 1973.2 | | HANNAH::OSMAN | see HANNAH::IGLOO$:[OSMAN]ERIC.VT240 | Thu May 25 1995 10:59 | 36 |
|
> How many operations are required to sort any string of length n, where
> each operation is a reversal of the first k characters?
As written, for any k < n, then *no* number of operations will work.
For example, consider this string:
4321
That's n=4.
Consider k=3.
Reverse:
2341
Reverse:
4321
Reverse:
2341
Bored yet ?
Clearly we'll never produce 1234 with k=3.
Am I misreading, or is problem mistated ? Help !
Thanks.
/Eric
|
| 1973.3 | pointer | HERON::BUCHANAN | Et tout sera bien et | Thu May 25 1995 11:19 | 3 |
| This is addressed in 425.*
Andrew.
|
| 1973.4 | | AUSSIE::GARSON | achtentachtig kacheltjes | Thu May 25 1995 22:53 | 14 |
| re .2
Your interpretation is a reasonable literal interpretation but not I
think the one intended by the originator of the problem.
The number of characters involved in each reversal is not a constant.
That is, I can reverse the first 5 (say) characters on the first
reversal and then reverse the first 2 (say) characters on the second
reversal.
"How many operations are required to sort any string of length n, where
each operation is a reversal of some prefix of the string." may come
closer to the intended meaning.
|
| 1973.5 | | RTL::GILBERT | | Fri May 26 1995 16:51 | 5 |
| .0> Rodriguez reports a claim this never requires more than n operations.
.0> Is that true?
No. The table in 425.4 shows that for n in {4,5}, n flips may be required;
and for n in {6,7,8}, n+1 flips may be required.
|