00001 #include "MusimatChapter9.h" 00002 MusimatChapter9Section(C091204b) { 00003 Print("*** Shuffle ***"); 00004 /***************************************************************************** 00005 00006 Shuffle 00007 00008 We can create a random permutation of a row rather as one would shuffle a deck of cards. 00009 If we distinguish between the cards and their position in the deck, shuffling consists of swapping 00010 the positions of all cards a pair at a time. First, we need a way to swap the position of two cards 00011 in the deck. We can swap the position of two elements in IntegerList like this: 00012 *****************************************************************************/ 00013 para1(); // Step into this function to continue. 00014 para2(); // Step into this function to continue. 00015 } 00016 00017 IntegerList swap(IntegerList L, Integer from, Integer to) { 00018 Integer x = L[to]; // save target value 00019 L[to] = L[from]; // swap from Æ to 00020 L[from] = x; // swap to Æ from 00021 Return(L); 00022 } 00023 00024 Static Void para1() { 00025 /***************************************************************************** 00026 To shuffle an entire deck of cards (or row of pitch classes), we visit each position in the list from 00027 first to last in order and swap the card at each position with a card at a randomly chosen other 00028 position. Because we use Random() to choose the position of the other card to swap, the "other" 00029 position can be any position in the deck, including the currently selected position; thus we may 00030 occasionally swap a card with its own position, leaving it where it was. However, in a subsequent 00031 step, that card might be chosen to be swapped elsewhere. 00032 *****************************************************************************/ 00033 } 00034 00035 IntegerList shuffle(IntegerList L) { 00036 IntegerList M = randomRow(Length(L)); // elements to swap 00037 For (Integer i = 0; i < Length(L); i = i + 1) { 00038 Integer j = M[i]; 00039 L = swap(L, i, j); 00040 } 00041 Return(L); 00042 } 00043 00044 Static Void para2() { 00045 /***************************************************************************** 00046 The first step is to generate a new row with randomRow(), which is stored in IntegerList M. 00047 Successive values of i and successive elements of M give the indexes of the elements in L that are 00048 to be swapped. Suppose we have 00049 00050 L = {0, 6, 2, 9, 7, 5, 4, 10, 8, 3, 1, 11}; // source row 00051 00052 M = {5, 1, 0, 4, 6, 7, 9, 3, 10, 8, 11, 2}; // row created in shuffle 00053 00054 Then each row in table 9.6 shows the intermediate values of L as its elements are being swapped. The 00055 pattern starts out like this: swap the value in position 0 and the value in position 5; swap the value 00056 in position 1 with itself; swap the value in position 2 and the value in position 0; swap the value in 00057 position 3 and the value in position 4; and so on. The result is that every element of the input row is 00058 swapped randomly with another element, but there's a chance it might be swapped with itself. 00059 *****************************************************************************/ 00060 00061 Print("*** Shuffling a row ***"); 00062 IntegerList x = IntegerList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9); 00063 Print("A row:", x); 00064 Print("Same row after shuffling:", shuffle(x)); 00065 00066 } 00067 00069 /* $Revision: 1.3 $ $Date: 2006/09/05 08:02:46 $ $Author: dgl $ $Name: $ $Id: C091204b.cpp,v 1.3 2006/09/05 08:02:46 dgl Exp $ */ 00070 // The Musimat Tutorial © 2006 Gareth Loy 00071 // Derived from Chapter 9 and Appendix B of "Musimathics Vol. 1" © 2006 Gareth Loy 00072 // and published exclusively by The MIT Press. 00073 // This program is released WITHOUT ANY WARRANTY; without even the implied 00074 // warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00075 // For information on usage and redistribution, and for a DISCLAIMER OF ALL 00076 // WARRANTIES, see the file, "LICENSE.txt," in this distribution. 00077 // "Musimathics" is available here: http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=10916 00078 // Gareth Loy's Musimathics website: http://www.musimathics.com/ 00079 // The Musimat website: http://www.musimat.com/ 00080 // This program is released under the terms of the GNU General Public License 00081 // available here: http://www.gnu.org/licenses/gpl.txt 00082