- Main Page
- Namespaces
- Files

- File List
- File Members

# C:/Musimathics_local/Musimat/MusimatChapter9/C090903.cpp

Go to the documentation of this file.

    00001 #include "MusimatChapter9.h"
    00002 MusimatChapter9Section(C090903) {
    00003 Print("*** 9.9.3 Circular Permutation ***");
    00004 /*****************************************************************************
    00005
    00006 9.9.3 Circular Permutation
    00007
    00008 A circular permutation, or rotation, occurs when the element at one end is
    00009 lopped off and attached to the other end circularly (figure 9.9). There are n
    00010 circular permutations of n objects. Rotation can be to the left or right by
    00011 one or more places.
    00012
    00013 Here is a method that rotates a list by an arbitrary number of places either
    00014 to the right or left.
    00015 *****************************************************************************/
    00016         para1(); // Step into this function to continue.
    00017 }
    00018
    00019 Void rotate(IntegerList Reference f, Integer n, Integer i = 0){
    00020         n = Mod(n, Length(f));                                          //constrain rotation to length of list
    00021         Integer x = f[i];                                                       //store f[i] for use after recursion
    00022         If(i < Length(f)-1)                                                     // reached the end?
    00023                 rotate(f, n, i+1);                                              // no, call rotate() recursively
    00024         // continue from here when the recursion unwinds
    00025         Integer pos = PosMod(i+n, Length(f));           // index list modulo its length
    00026         f[pos] = x;                                                                     // assign value of x saved above
    00027 }
    00028
    00029 Static Void para1() {
    00030 /*****************************************************************************
    00031 This example uses recursion to perform its function. It takes three arguments,
    00032 a list f, the number n of positions to rotate by, and i, the index for where
    00033 to begin, usually set to zero. If n is positive, the list is rotated to the
    00034 right that many places; if n is negative, the list is rotated that many
    00035 positions to the left. The first step is to constrain n modulo the length
    00036 of the list so that any amount of rotation can be handled.
    00037 The declaration IntegerList Reference f requires a bit of explanation. We
    00038 want Rotate() to modify the list that is supplied. But functions are
    00039 ordinarily supplied only with copies of the value of the actual arguments
    00040 (see appendix B, B.1.22). The word Reference in the declaration tells
    00041 Musimat that it should supply Rotate() with the actual variable named when
    00042 the function is invoked. Thus changes to the list handed to Rotate() will
    00043 persist after the function is finished.
    00044 We need to make sure the variable pos stays within the range of valid list
    00045 elements, which naturally suggests the use of Mod(), except that Mod() can
    00046 return negative values. But list indexes must be strictly positive. So we
    00047 use a function called PosMod(), which returns only the positive wing of
    00048 modulo values (see appendix A.6).
    00049
    00050 "Musimat" V1 Table 9.3 shows left and right rotation by various amounts for a list
    00051 iL defined as follows.
    00052 *****************************************************************************/
    00053
    00054         Print("*** Rotate examples ***");
    00055         IntegerList iL = IntegerList(0, 1, 2, 3, 4, 5);
    00056         Print("Starting list:", iL);
    00057         Print("Successive forward rotations by 1:");
    00058
    00059         For (Integer i = 0; i < Length(iL); i = i + 1) {
    00060                 rotate(iL, 1);
    00061                 Print(iL);
    00062         }
    00063
    00064         Print("Backward rotations by 1:");
    00065         For (Integer i = 0; i < Length(iL); i = i + 1) {
    00066                 rotate(iL, -1);
    00067                 Print(iL);
    00068         }
    00069
    00070 }}
    00071
    00073 /* $Revision: 1.2 $ $Date: 2006/09/09 06:22:41 $ $Author: dgl $ $Name:  $ $Id: _c090903_8cpp-source.html,v 1.2 2006/09/09 06:22:41 dgl Exp $ */
    00074 // The Musimat Tutorial © 2006 Gareth Loy
    00075 // Derived from Chapter 9 and Appendix B of "Musimathics Vol. 1" © 2006 Gareth Loy
    00076 // and published exclusively by The MIT Press.
    00077 // This program is released WITHOUT ANY WARRANTY; without even the implied
    00078 // warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
    00079 // For information on usage and redistribution, and for a DISCLAIMER OF ALL
    00080 // WARRANTIES, see the file, "LICENSE.txt," in this distribution.
    00081 // "Musimathics" is available here:     http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=10916
    00082 // Gareth Loy's Musimathics website:    http://www.musimathics.com/
    00083 // The Musimat website:                 http://www.musimat.com/
    00084 // This program is released under the terms of the GNU General Public License
    00085 // available here:                      http://www.gnu.org/licenses/gpl.txt