You are here

Parity Theorem for Permutations - Demonstration Software

John O. Kiltinen

The development to this point is well known. What comes now is new: an approach to the Reduction Lemma based on hands-on experience doing transpositions with objects, not notation. The approach is also supported by a computer program that allows the student to gain experience with the algorithm underlying the proof of the Reduction Lemma. We will postpone stating the rules for the algorithm and its proof until after we explore the algorithm a bit by means of the software.

Figure 2 shows the user interface for our Parity Theorem Demo program. (In the Macintosh implementation, the menu bar shown here is not in the window of the program but instead the menu items shown are included on the main menu bar at the top of the screen.) One sees a set of twelve numbered boxes that contain two sets of numbered markers. The human user of the software performs transpositions on the green markers on the left side. This is done simply by “dragging” a green marker from one box to another with the pointer and with the mouse button depressed. When the drag reaches the destination box and one releases the mouse button, the computer will swap the green markers between the source box and the destination box.

While the human user is performing transpositions with the green markers on the left, the computer is doing the same with the blue markers on the right. In the initial “Human First” mode, the computer reacts to the transpositions that the human user enters by producing a second sequence of transpositions that will ultimately use two fewer of them when all markers are returned to their home boxes. After learning the algorithm, the human user can confirm an understanding of it by switching to “Computer First” mode wherein the computer generates a sequence of transpositions and the human user produces the shorter sequence.

The program is available in versions for both the Macintosh and Windows platforms, and can be downloaded by the interested reader. Detailed online instructions are included and are accessed from the “Help” menu. The program also does an automated demonstration, which the user initiates with a command from the “Action” menu.

Figure 2 gives insight into the shortening algorithm. It reflects the state after the human user has performed four transpositions, namely, (1, 8), (6, 7), (12, 5), and (6, 1) in that order. (Note that the numbers refer to the boxes involved in each swap, not the numbers of the markers being swapped.)

After the first transposition was performed, the computer marked box number 1 as the “First Box” by highlighting its background in gold, and it marked box number 8 as the “Tagged Box” by highlighting its background in beige, but it did no transposition on the blue markers. It responded to the next three transpositions by performing the sequence (6, 7), (12, 5), and (6, 8) on the blue markers.

Note that the human user’s fourth transposition (6, 1) on the green markers moved marker 7 from box 6 into the First Box number 1 and moved green marker 8 out of box 1 and into box 6. The computer avoided a transposition involving the First Box but instead responded by moving blue marker 7 from box 6 into the Tagged Box number 8 while moving marker 8 that had been there into box 6. After these two sequences of transpositions, the arrangements of the green and blue markers are the same except for the ones in the highlighted First and Tagged Boxes. The computer is “ahead of the game,” however, in terms of returning to the identity arrangement because it has its marker in the First Box being the one that is at home there.

The reader may find it useful to try out the demonstration program for a few minutes before reading further. As is the case with most algorithms, one learns this one more easily be seeing it in action than by reading the rules for it.

John O. Kiltinen, " Parity Theorem for Permutations - Demonstration Software," Convergence (December 2004)