#include "MusimatChapter9.h"Go to the source code of this file.
Functions | |
| MusimatChapter9Section (C090903) | |
| Void | rotate (IntegerList Reference f, Integer n, Integer i=0) |
| Static Void | para1 () |
| MusimatChapter9Section | ( | C090903 | ) |
Definition at line 2 of file C090903.cpp.
References para1().
{
Print("*** 9.9.3 Circular Permutation ***");
/*****************************************************************************
9.9.3 Circular Permutation
A circular permutation, or rotation, occurs when the element at one end is
lopped off and attached to the other end circularly (figure 9.9). There are n
circular permutations of n objects. Rotation can be to the left or right by
one or more places.
Here is a method that rotates a list by an arbitrary number of places either
to the right or left.
*****************************************************************************/
para1(); // Step into this function to continue.
}
| Static Void para1 | ( | ) |
Definition at line 29 of file C090903.cpp.
References rotate().
{
/*****************************************************************************
This example uses recursion to perform its function. It takes three arguments,
a list f, the number n of positions to rotate by, and i, the index for where
to begin, usually set to zero. If n is positive, the list is rotated to the
right that many places; if n is negative, the list is rotated that many
positions to the left. The first step is to constrain n modulo the length
of the list so that any amount of rotation can be handled.
The declaration IntegerList Reference f requires a bit of explanation. We
want Rotate() to modify the list that is supplied. But functions are
ordinarily supplied only with copies of the value of the actual arguments
(see appendix B, B.1.22). The word Reference in the declaration tells
Musimat that it should supply Rotate() with the actual variable named when
the function is invoked. Thus changes to the list handed to Rotate() will
persist after the function is finished.
We need to make sure the variable pos stays within the range of valid list
elements, which naturally suggests the use of Mod(), except that Mod() can
return negative values. But list indexes must be strictly positive. So we
use a function called PosMod(), which returns only the positive wing of
modulo values (see appendix A.6).
"Musimat" V1 Table 9.3 shows left and right rotation by various amounts for a list
iL defined as follows.
*****************************************************************************/
Print("*** Rotate examples ***");
IntegerList iL = IntegerList(0, 1, 2, 3, 4, 5);
Print("Starting list:", iL);
Print("Successive forward rotations by 1:");
For (Integer i = 0; i < Length(iL); i = i + 1) {
rotate(iL, 1);
Print(iL);
}
Print("Backward rotations by 1:");
For (Integer i = 0; i < Length(iL); i = i + 1) {
rotate(iL, -1);
Print(iL);
}
}
| Void rotate | ( | IntegerList Reference | f, |
| Integer | n, | ||
| Integer | i = 0 |
||
| ) |
Definition at line 19 of file C090903.cpp.
References rotate().
{
n = Mod(n, Length(f)); //constrain rotation to length of list
Integer x = f[i]; //store f[i] for use after recursion
If (i < Length(f)-1) // reached the end?
rotate(f, n, i+1); // no, call rotate() recursively
// continue from here when the recursion unwinds
Integer pos = PosMod(i+n, Length(f)); // index list modulo its length
f[pos] = x; // assign value of x saved above
}
1.7.2