| Re: Elementary but surprisingly difficult. |
|
 |
|
 |
|
 |
|
 |
Group: comp.lang.forth · Group Profile
Author: Marc OlschokMarc Olschok Date: Jun 2, 2008 11:06
John Passaniti japanisshinto.com> wrote:> Jonah Thomas wrote:
>> How do we even decide what it means to preserve the original order
>> when we remove some items? abcde keeps a subset that's in the
>> original order. bdeca does also.
>
> I didn't have any problem at all defining order. Again, the original
> message from Albert-- the one I first replied to-- described the problem
> as removing duplicates from an array. Now I hate to get all Computer
> Science on everyone, but the very definition of array denotes an
> ordering; you can say the "first" item in an array, and it has clear and
> unambiguously meaning.
>
> So no, if preserving the original order mattered, "bdeca" wouldn't work,
> because the original order had a "a" as the *first* element.
By that reasoning, your original solution of reducing "abcbdecadec"
to "abcde" also does not work because the original order had "d"
as the *fifth* element.
So perhaps it is not that obvious from the notion of array,
what kind of order is to be understood.
Of course an array can be identified with a map f: I --> X
from a linear ordered index set I to a set X describing the possible
entries. In this way, the map f "is" the order; but then no true reduction
would preserve it.
Another choice is the "order of first appearance", where an order
is imposed on f(I) via
x < y <==> min{ i in I | f(i)=x } < min{ i in I | f(i)=y }
With respect to this order the word "abcbdecadec" gives
a < b < c < d < e
So your solution "abcde" does preserve it but "bdeca" does not.
Marc
| 
