<div dir="auto">From time to time EM contributers have described simple ways to construct the Smith set.<div dir="auto"><br></div><div dir="auto">Here's another one that just occurred to me:</div><div dir="auto"><br></div><div dir="auto">1. Make a list L1 of the candidates in any order ... the order they appear on the ballot will do.</div><div dir="auto">2. Reverse L1 to get L2.</div><div dir="auto">3. Bubble Sort each of these two lists pairwise (separately) to get sorted lists SL1 and SL2, respectively.</div><div dir="auto">4. The Smith Set is the smallest solid coalition contained in both sorted lists.</div><div dir="auto">5. This set is easily found by placing the sorted lists side- by-side and slowly lowering a line until the same set of candidates is above the line in both lists.</div><div dir="auto">5. More systematically ... find the tops t1 and t2 of each list in the other list ... then form a beatpath that starts at t1 completes a cycle through the Smith set by continuing down to t2 ... then connecting to t2 at the top of the second list ... and continuing down that list to t1 ... thereby completing a beattcycle through the Smith Set.</div><div dir="auto">6. Check that this set is the Smith Set by starting at any point of the beatcycle we just constructed .... making one complete circuit through it ... and then continuing down either list SL1 or SL2 to extend the beatpath to the rest of the candidates.</div><div dir="auto"><br></div><div dir="auto">In summary... starting at any candidate in our "top cycle" we get a beatpath through all of the other candidates ... therefore our top cycle contains the Smith set, defined as the smallest set of candidates all of whom have beatpaths to the remaining candidates.</div><div dir="auto"><br></div><div dir="auto">It is clear that no smaller solid coalition would include both t1 and t2 ... which must be included in Smith or they could not bubble sort to the top.</div><div dir="auto"><br></div><div dir="auto">It sounds complicated ... but it's easy to do... just list the candidates in the same order they appear on the ballot ... then reverse the list to get a second list ... then bubble sort both lists.</div><div dir="auto"><br></div><div dir="auto">If both lists have the same top candidate t1=t2, then that candidate is the CW. If not find t1 in the second list and t2 in the first list ... the beatpath from t1 to t2 in the first list concatenated with the beatpath from t2 to t1 in the second list is the "top cycle" we're looking for.</div><div dir="auto"><br></div><div dir="auto">-Forest</div></div>