# Calculating the Smith set?

Steve Eppley seppley at alumni.caltech.edu
Sat Apr 20 16:55:43 PDT 1996

[The EM list is again having troubles.  Four of my posts bounced back
to me with "unknown mailer error 14".  I'm attempting to repost them.]

Steve E wrote [a Smith algorithm]:
>>    Find the candidate(s) with the fewest pairwise defeats.  (These
>>    candidate(s) are guaranteed to be in the Smith set.)  Create
>>    a list named Smith with just these candidate(s).
>>
>>    for each candidate Ci in the (growing) Smith list
>>       for each candidate Cj
>>          if Ci did not pairwise-beat Cj
>>             if Cj is not yet in the Smith list
>>                append Cj to the Smith list
>>             endif
>>          endif
>>       endfor
>>    endfor

Bruce A replied:
>It may not work--the line "append Cj to the Smith list" is too vague.

It wasn't vague to me, but this appears to be another instance of
Eppley's First Law of Communication: "The worst judge of how a
message will be interpreted is its author."

To a programmer, "list" and "append" have meanings which may not be
apparent to everyone.  Lists are ordered and have a first element
and a last element.  When a new element is appended to a list, it
is appended at the end and becomes the new last element.

Another property of lists is that the pointer (a.k.a. address) to a
list's first element can always be obtained.  Another property is
that given a pointer to an element of a list there is a way to find
the pointer to the next element.  (Attempting to find the pointer to
the next element after the last element returns a special "null"
pointer.)  So lists can be traversed from first to last.

If there was any vagueness, I think it would be in the line:
"for each candidate Ci in the (growing) Smith list"
I'm implying that the candidates would be traversed from the first
candidate of the list, in list order, until the "null" pointer is
returned by the attempt to find the next candidate.

When coded in a standard programming language instead of pseudocode,
there will be no vagueness.

--Steve