Paul Gilmartin writes:
<begin snippet>
"multiset" or "tuple"? Wikipedia (which, as you know, is always right) says for
"multiset":
In multisets, as in sets and in contrast to tuples,
the order of elements is irrelevant ...
so "preserv[ing] the original ordering" is an empty notion.
</end snippet>
and in so doing he has provided a textbook illustration of some of the maladies
of the net.
The classic sorting reference is:
Knuth, Donald E., The art of computer programming, volume 3, sorting and
searching. Reading, MA: Addison-Wesley, various editions, 1974+.
In it Mr. Gilmartin will find section 5.1.2. Permutations of a multiset. A
multiset is much like a set except that it may contain duplicate elements. One
thus speaks of an ordered set or a partially ordered multiset. Passim in this
volume Knuth uses this terminology, and it is standard elsewhere too. The
standard set-theory text--What is its title Mr. Gilmartin?--abounds in
references to sets that are geordnete and multisets that are teilweise
geordnete.
An ordered set O of n elements thus takes the form
O = {s(1) < s(2) < s(3) < . . . < s(i) < . . . < s(n)},
and a partially ordered multiset of m elements takes the form
P = {p(1) <= p(2) <= p(3) <= . . . <= p(j) <= . . . <= p(m)}.
If now for some subsequence of s elements of such a partially ordered/sorted
multiset we have
p(k) = p(k+1) = . . . = p(k+s-1)
we can ask the question: Are these elements of s in the same sequence in which
they appeared in this multiset before it was sorted? This question is
sometimes important, sometimes not; but it is never meaningless.
I have no real quarrel with Mr. Gilmartin's wish to épater John Gilmore, but in
this case and others he has felt free to suggest that I don't know what I am
talking about without doing his homework. Here he quite literally has no
notion of what he is talking about.
His gadfly role here is a drôle and sometimes even useful one, but it is time
for him to learn that Wikipedia, which is I suppose a suitable source from
which to crib a secondary-school book review, cannot always be relied upon to
meet more exigent requirements.
John Gilmore Ashland, MA 01721-1817 USA
