Basics III: Permutation1
The Introduction defines what permutations are, then describes how any permutation
can be represented as a non-repeating succession of integers. The representation is fleshed out
by demonstrating how a permutation represented in this manner can be used to rearrange a set of toy animals.
Categories of Permutation describes different varieties of permutation, including
Identity, Retrograde,
Transposition,
Multiplication,
Rotation,
pairwise exchanges in Change Ringing,
Random Shuffling,
and permutations which undo other permutations.
The closing topic, Coding, develops two Java classes implementing permutations
in different ways. The Permutation
class implements the succession-of-integers representation. This takes the basically passive approach of
converting array-lookup indices from an original order to a permuted order. The
Sequence
class
implements active approach of presenting set elements in succession, employing the
hasNext()/next()
design
of java.lang.Iterator.
Sequence
does not directly implement permutations, but
it does employ permutational devices to enrich the variety of presentation orders.
The overview to this site's entire topic area on Sequence Generation in Java listed
order and content as "the two most fundamental criteria for evaluating a sequence generator".
The present page drills into order by generalizing the means by which values can be drawn from a
source set.
Wikipedia defines a set
as "a collection of different things". Wikipedia further defines a
permutation
as "an arrangement" of the elements of a set, or "if the set is already ordered, a rearrangement".
Permutations are a favorite subject of investigation for mathematical
group theory. We will not be
making any use of group theory here; the practice of counting from 0 (rather than 1) is consistent with
with modern programming practice but not with my college textbook on group theory.2
Any permutation can be represented as a non-repeating succession (normally one would use the word "sequence", but
"sequence" is here being reserved for a different purpose) of indices, which are in turn
suitable for looking up set elements from an array or collection. As such, indices must be non-negative
integers.
The position of an element in the succession indicates the move-from position in the old order, while
the value of the element indicates the move-to position in the
new order. The length of the succession must match the size of the set being permuted.
This sequential representation has the advantage of compactness but the visual disadvantage that
the move-from positions are implicit; however, that disadvantage is not of great consequence to
a computer implementation.
Think of the representation this way: You have a set of five toy farm animals: {horse, cow, pig, sheep, dog}.
Suppose there are two rows of five cubbies, stacked above one another, each numbered from 0 (leftmost) to 4
(rightmost). Initially the toy animals are stored in the top row with the horse in cubby #0,
the cow in cubby #1, the pig in cubby #2, the sheep in cubby #3, and the dog in cubby #4. Then the
permutation (3 0 1 4 2) represents the following actions:
-
Move the horse from cubby #0 in the top row to cubby (3 0 1 4 2) in the bottom row: {_, _, _, horse, _}.
-
Move the cow from cubby #1 in the top row to cubby (3 0 1 4 2) in the bottom row: {cow, _, _, horse, _}.
-
Move the pig from cubby #2 in the top row to cubby (3 0 1 4 2) in the bottom row: {cow, pig, _, horse, _}.
-
Move the sheep from cubby #3 in the top row to cubby (3 0 1 4 2) in the bottom row: {cow, pig, _, horse, sheep}.
-
Move the dog from cubby #4 in the top row to cubby (3 0 1 4 2) in the bottom row: {cow, pig, dog, horse, sheep}.
The result will be that all five toy animals have been moved to the bottom row of cubbies.
The cow will be in cubby #0. The pig will be in cubby #1. The dog will be in
cubby #2. The horse will be in cubby #3. The sheep will be in cubby #4.
Keep in mind that the integers in (3 0 1 4 2) indicate positions in a specific way of presenting
the set's elements. What's confusing is that integers can also identify specific set elements, e.g.
{X0, X1, X2, …}.
So when you see the integers in parentheses, you should think relative positions. When you see the
integers as subscripts, you should think absolute identifiers. Where Wikipedia writes about
"an arrangement" of an (implicitly unordered) set it's mapping from identifier apples to positional oranges. What what I'm
writing about here is strictly about "rearrangement", that is, mapping old positions to new positions.
In the survey which follows the symbol N indicates the permutation length. Positions must therefore
range from 0 to N-1.
A major source from which the permutation categories surveyed here are drawn is serialism,
a method of musical composition favored by post World-War-II composers, based upon earlier practices developed by
Arnold Schoenberg. Among
other things, serialism sought to achieve unity
by deriving material from an "original" arrangement of the twelve chromatic degrees. This "original" arrangement was called the "row", the "set", or
the "series", and the methods of derivation were permutations of this "original".
Gottfried Michael Koenig's Project2 program for musical composition directly comes out of
the serialist tradition.
Permutations also figure prominently in the "system" of
Joseph Schillinger, who attempted to formulate a
mathematical basis for the arts during the 1930's.
The identity permutation keeps each sample element in the same position, for example (0 1 2 3 4).
For any given number of set elements, just the one ascending succession of integers can
represent the identity permutation. In music
the identity permutation corresponds to the twelve degrees of the chromatic scale, presented in ascending
order. The "original" series form in serialism does
not correspond to the identity permutation.
The retrograde permutation reverses the sample order, for example (4 3 2 1 0).
For any given number of set elements N, just the one descending succession of integers can
represent the retrograde permutation. The "retrograde"
series form in serialism can be derived by
applying the retrograde permutation to the original series form.
I'm not sure if this category of permutation has an official name, but it involves advancing the
index by a fixed increment each time a member is dereferenced. For example, (0 2 4 1 3) employs
an increment of 2. An increment of 1 and a starting index of 0 gives
identity order: (0 1 2 3 4); an increment of
-1 gives reverse order (0 4 3 2 1) but this is different from retrograde.
To make it retrograde the starting index has to be 4 (-1 mod 5), not 0.
Transposition is one method of deriving a new permutation from an existing one. Each member of the
derived permutation is obtained by adding a fixed offset and applying modulo N arithmetic to
wrap around values which otherwise threaten to go outside the range from 0 to N-1.
For the chromatic scale, where N=12, twelve separate
transpositions are possible:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 |
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 | 1 |
3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 | 1 | 2 |
4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 | 1 | 2 | 3 |
5 | 6 | 7 | 8 | 9 | 10 | 11 | 0 | 1 | 2 | 3 | 4 |
6 | 7 | 8 | 9 | 10 | 11 | 0 | 1 | 2 | 3 | 4 | 5 |
7 | 8 | 9 | 10 | 11 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
8 | 9 | 10 | 11 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
9 | 10 | 11 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
10 | 11 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
11 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
The transposition with offset 0 being the identity permutation. In
serialism these twelve permutations can be applied (1) to the "original" series
form, (2) to the retrograde of the "original", (3) to the chromatic inversion (see Multiplication below) of the "original",
or (4) to the retrograde-inversion. These are the derivations which Schoenberg allowed, making a total of 48 orthodox serial derivations.
Multiplication is another method of deriving a new permutation from an existing one. Each member of the
derived permutation is obtained by applying a fixed multiplier and applying modulo N arithmetic to
wrap around values which otherwise threaten to go outside the range from 0 to N-1.
For the chromatic scale, where N=12, only four different multipliers map the chromatic scale fully back onto
itself. These multipliers are 1, 5, 7, and 11 (all relatively prime to 12):
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
0 | 5 | 10 | 3 | 8 | 1 | 6 | 11 | 4 | 9 | 2 | 7 |
0 | 7 | 2 | 9 | 4 | 11 | 6 | 1 | 8 | 3 | 10 | 5 |
0 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
A multiplication factor of 1 gives back the identity transformation, while a factor of 11 produces chromatic inversion (not to be confused with
permutational inversion which is something different entirely). A factor of 7, when mapped to degrees
of the chromatic scale, produces an artifact familiar to musicians as the circle of fifths.
A factor of 5 gives the circle of fourths, which is the chromatic inversion of the circle of fifths.
Composer Charles Wuorinen (a die-hard serialist) has added factor-of-7 multiplication to the suite of allowable derivations from
the original series form. For each successive interval in the series, factor-of-7 multiplication amounts to expanding each
semitone of the original interval into a perfect fifth. Which means that there will be very little resemblence to the "original"
contour. It also means that minor seconds and major sevenths (classified as strong dissonances) exchange with
perfect fifths and perfect fourths (classified as open consonances).
Rotation permutations move set elements some number of positions to the left or right, wrapping around
positions which otherwise threaten to go outside the range from 0 to N-1. For examples:
-
(1 2 3 4 0) rotates each sample element one position to the right, wrapping the element in the
final old position to the initial new position.
-
(4 0 1 2 3) rotates each sample element one position to the left, wrapping the element in the
initial new position to the final old position.
-
(3 4 0 1 2) rotates each sample element three positions to the right, wrapping elements as necessary.
Rotations play a major role in the Schillinger System. They were also
used by Igor Stravinsky as an non-orthodox (that is, not prescribed by Schoenberg) mechanism for deriving series
forms.3
Change ringing operates with a set of bells initially ranging from highest pitched to lowest pitch.
The plain hunt method of change ringing alternates two different permutations, outer and inner:
-
The outer exchange switches each consecutive pair of set elements, for example (1 0 3 2 5 4).
-
The inner exchange retains the initial and final elements in the same position, but switches the remaining
pairs, for example (0 2 1 4 3 5).
It happens that if the change ringers keep alternating outer exchanges with inner exchanges, they eventually
come back to the initial high-to-low order. Wikipedia also describes other methods.
Referring back to the toy-animal scenario described above, random shuffling works like this:
First you mark the integers from 0 to 4 on a set of 5 equal-sized white marbles. Dump these marbles
in an urn and mix them around blindly. Take the horse from top-row cubby #0. Draw a marble
from the urn. Use the number marked on the marble to select which bottom-row cubby to place
the horse in. Set the marble aside so it can't be drawn again. Next take the cow from cubby
#1. Draw a second marble, use it to select an empty bottom-row cubby, then set the second
marble aside. Continue on until all five toy animals have been moved to bottom-row cubbies.
If a set contains N elements, then there are N×(N-1)×…×1=N!
ways of shuffling the set randomly and the likelihood of any one specific outcome is 1/N!.
For five toy animals N!=5×4×3×2×1=120. Thus the likelihood
that random shuffling will leave the presentation order alone (applying the
identity permutation 0 1 2 3 4) is 1/120≈0.008.
Additionally, the likelihood that random shuffling will reverse the presentation order (applying the
retrograde permutation 4 3 2 1 0) is also 1/120≈0.008.
Random shuffling is an option of Koenig's Project2, and harkens back
to the Gesang der Jünglinge,
an iconic tape piece upon which Koenig collaborated, where tape segments were drawn blindly from a box.
This is yet another method of deriving a new permutation from an existing one. Every permutation has an
inverse permutation which undoes what the original did. The inverse may
be derived notationally from the original by iterating through the original values from 0 to N-1 and
by listing the position of each value. For example to undo (3 0 1 4 2):
-
(3 0 1 4 2) maps position 1 to position 0, so the 0th inverse value must be 1.
-
(3 0 1 4 2) maps position 2 to position 1, so the 1st inverse value must be 2.
-
(3 0 1 4 2) maps position 4 to position 2, so the 2nd inverse value must be 4.
-
(3 0 1 4 2) maps position 0 to position 3, so the 3rd inverse value must be 0.
-
(3 0 1 4 2) maps position 3 to position 4, so the 3rd inverse value must be 3.
The inverse of the permutation (3 0 1 4 2) is therefore (1 2 4 0 3). Remember that a permutation
is also a set, so is itself subject to permutation. Consider what happens when
the permutation (1 2 4 0 3) rearranges the source set {3, 0, 1, 4, 2}:
-
0th set element 3 permutes to (1 2 4 0 3): {0, _, _, _, _}
-
1st set element 0 permutes to (1 2 4 0 3): {0, 1, _, _, _}
-
2nd set element 1 permutes to (1 2 4 0 3): {0, 1, 2, _, _}
-
3rd set element 4 permutes to (1 2 4 0 3): {0, 1, 2, 3, _}
-
4th set element 2 permutes to (1 2 4 0 3): {0, 1, 2, 3, 4}
Thus (3 0 1 4 2) permuted by (1 2 4 0 3) produces the identity permutation (0 1 2 3 4). And what
was just shown for (3 0 1 4 2) and its inverse (1 2 4 0 3) is generally true: permuting
any original permutation by the original permutation's inverse produces the identity permutation.
Some examples from permutations previously surveyed: The retrograde permutation is
its own inversion. For the chromatic scale, transposition by an offset modulo(-K,12) undoes transposition by offset K. Likewise
multiplication by multiplier modulo(-M,12) undoes multiplication by multiplier M. Rotating a permutation
K positions to the left is undone by rotating K positions to the right.
/**
* The {@link Permutation} class implements an array of integers with
* two properties:
* All values fall within the range from 0 (inclusive) to the array
* length (exclusive).
* No value appears more than once in the array.
* @author Charles Ames
*/
public class Permutation
extends WriteableEntity {
/**
* A 12-member permutation where member(i) = modulo(member(i-1)+7, 12).
*/
private static final Integer[] circleOfFifthsMap
= {0, 7, 2, 9, 4, 11, 6, 1, 8, 3, 10, 5};
/**
* Helper class to serially manipulate members.
* @author Charles Ames
*/
private class MemberIterator
implements Iterator<Integer> {
private int length;
private int index;
private int position;
private int increment;
private int multiplier;
private int transposition;
public MemberIterator(int start, int increment, int multiplier, int transposition) {
this.length = Permutation.this.itemCount();
this.position = MathMethods.modulo(start, length);
this.increment = MathMethods.modulo(increment, length);
if (MathMethods.gcd(this.increment, length) != 1)
throw new IllegalArgumentException("Intended position increment "
+ increment + " not relatively prime to length " + length);
this.multiplier = MathMethods.modulo(multiplier, length);
if (MathMethods.gcd(this.multiplier, length) != 1)
throw new IllegalArgumentException("Intended value multiplier "
+ multiplier + " not relatively prime to length " + length);
this.transposition = MathMethods.modulo(transposition, length);
index = 0;
}
@Override
public boolean hasNext() {
return index < length;
}
@Override
public Integer next() {
int member = Permutation.this.memberAt(position);
int result = MathMethods.modulo((multiplier * member) + transposition, length);
System.out.println("position " + position + " member " + member + " result " + result);
position += increment;
index++;
return result;
}
}
private IntArray members;
private int place;
/**
* Constructor for {@link Permutation} entities with container.
* @param container The {@link WriteableEntity} which contains this permutation.
*/
public Permutation(EntityContainer container) {
super(container);
this.setIDQuality(AttributeQuality.MODIFIABLE);
this.setNameQuality(AttributeQuality.MODIFIABLE);
this.members = null;
}
/**
* Get the count of members.
* @return The assigned count of members.
*/
public int itemCount() {
if (null == members) throw new UninitializedException("Member count not initialized");
return members.itemCount();
}
/**
* Set the count of members.
* @param itemCount The intended count of members.
*/
public void setItemCount(int itemCount) {
this.members = new IntArray(itemCount);
for (place = 0; place < itemCount; place++) {
members.insertMember(Integer.MIN_VALUE, place);
}
this.place = 0;
makeDirty();
}
/**
* Set the next available position of this permutation
* to the indicated value. Positions are internally incremented.
* @param member The indicated value.
* @throws UnsupportedOperationException when all positions have been
* populated.
* @throws IllegalArgumentException when the indicated value falls
* outside the range from zero (inclusive) to the permutation length
* (exclusive).
* @throws UnsupportedOperationException when any new member
* duplicates an existing member.
*/
public void addMember(int member) {
int length = itemCount();
if (place >= length)
throw new UnsupportedOperationException("Members fully populated");
if (member < 0 || member >= length)
throw new IllegalArgumentException(
"Value " + member + " at position " + place
+ " outside range from 0 to " + (length-1));
int k = members.positionOf(member, place);
if (k >= 0)
throw new UnsupportedOperationException(
"Value " + member + " previously inerted at position " + k);
members.insertMember(member, place++);
makeDirty();
}
/**
* Set the map.
* @param map An integer array
* @throws IllegalArgumentException when any array element falls outside the
* range from 0 (inclusive) to the array length (exclusive), or when any integer
* value appears more than once in the array.
*/
public void setMembers(Integer[] map) {
int length = map.length;
setItemCount(length);
for (int index = 0; index < length; index++) {
addMember(map[index]);
}
makeDirty();
}
/**
* Fill this permutation with an ascending sequence of integers.
* @param itemCount The permutation length.
*/
public void fillAscending(int itemCount) {
setItemCount(itemCount);
for (int member = 0; member < itemCount; member++) {
addMember(member);
}
}
/**
* Get a {@link Permutation} instance representing a 12-member
* permutation where member(i) = modulo(member(i-1)+7, 12).
* @return The newly instantiated {@link Permutation} instance.
*/
public static Permutation getCircleOfFifths() {
Permutation permutation = new Permutation(null);
permutation.setMembers(circleOfFifthsMap);
return permutation;
}
/**
* Get a {@link Permutation} instance representing the outer
* exchange operation from change ringing.
* @param itemCount The cycle length;
* @return The newly instantiated {@link Permutation} instance.
*/
public static Permutation getOuterExchange(int itemCount) {
if (!MathMethods.even(itemCount))
throw new IllegalArgumentException("Member count not even");
Permutation permutation = new Permutation(null);
permutation.setItemCount(itemCount);
for (int position = 0; position < itemCount; position += 2) {
permutation.members.insertMember(position+1, position);
permutation.members.insertMember(position, position + 1);
}
return permutation;
}
/**
* Get a {@link Permutation} instance representing the inner
* exchange operation from change ringing.
* @param itemCount The cycle length;
* @return The newly instantiated {@link Permutation} instance.
*/
public static Permutation getInnerExchange(int itemCount) {
if (!MathMethods.even(itemCount))
throw new IllegalArgumentException("Member count not even");
Permutation permutation = new Permutation(null);
permutation.setItemCount(itemCount);
int last = itemCount - 1;
permutation.members.insertMember(0, 0);
for (int position = 1; position < last; position += 2) {
permutation.members.insertMember(position+1, position);
permutation.members.insertMember(position, position + 1);
}
permutation.members.insertMember(last, last);
return permutation;
}
/**
* Rearrange the members of a {@link Permutation} in place.
* @param target The {@link Permutation} whose members are to be permuted.
* @throws IllegalArgumentException when the target {@link Permutation}
* is sized differently than this.
*/
public void permute(Permutation target) {
int length = target.itemCount();
if (length != itemCount()) {
throw new IllegalArgumentException(
"Target item count " + length
+ " inconsistent with this item count " + itemCount());
}
IntArray scratch = target.members.copy();
target.setItemCount(length);
for (int position = 0; position < length; position++) {
int member = scratch.memberAt(position);
target.members.insertMember(memberAt(member), position);
}
}
/**
* Rearrange the elements of an array in place.
* @param target The array whose contents are to be permuted.
* @throws IllegalArgumentException when the target array is sized
* differently than this permutation.
*/
public void permute(Object[] target) {
int length = target.length;
if (length != itemCount()) {
throw new IllegalArgumentException(
"Target item count " + length
+ " inconsistent with this item count " + itemCount());
}
Object[] scratch = new Object[length];
for (int position = 0; position < length; position++)
scratch[position] = target[position];
for (int position = 0; position < length; position++)
target[memberAt(position)] = scratch[position];
}
/**
* Rearrange the elements of a {@link List} in place.
* @param target The {@link List} whose contents are to be permuted.
* @throws IllegalArgumentException when the target {@link List} is sized
* differently than this permutation.
*/
public void permute(List<Object> target) {
int length = target.size();
if (length != itemCount()) {
throw new IllegalArgumentException("Target item count " + length
+ " inconsistent with this item count " + itemCount());
}
Object[] scratch = new Object[length];
for (int position = 0; position < length; position++)
scratch[position] = target.get(position);
for (int position = 0; position < length; position++)
target.set(memberAt(position), scratch[position]);
}
/**
* Copy this {@link Permutation} to a fresh target instance, then replace
* (position, member) mappings with (member, position) mappings.
* This operation is different from musical inversion.
* @return The newly instantiated target instance.
*/
public Permutation invert() {
Permutation target = new Permutation(null);
int itemCount = itemCount();
target.setItemCount(itemCount);
for (int position = 0; position < itemCount; position++) {
int member = members.memberAt(position);
target.members.insertMember(position, member);
}
return target;
}
/**
* Copy this {@link Permutation} to a fresh target instance, then
* shift the members rightward the number of positions indicated.
* @param increment How far rightward to shift each member.
* Negative increments shift leftward.
* @return The newly instantiated target instance.
*/
public Permutation shiftRight(int increment) {
Permutation target = new Permutation(null);
int itemCount = itemCount();
target.setItemCount(itemCount);
for (int position = 0; position < itemCount; position++) {
int member = members.memberAt(position);
int newPosition = MathMethods.modulo(position+increment, itemCount);
target.members.insertMember(member, newPosition);
}
return target;
}
/**
* Copy this {@link Permutation} to a fresh target instance, then
* add an offset to each member using modulo N arithmetic.
* @param offset How much to add to each member.
* @return The newly instantiated target instance.
*/
public Permutation transpose(int offset) {
Permutation target = new Permutation(null);
int itemCount = itemCount();
target.setItemCount(itemCount);
for (int position = 0; position < itemCount; position++) {
int member = members.memberAt(position);
member = MathMethods.modulo(member+offset, itemCount);
target.members.insertMember(member, position);
}
return target;
}
/**
* Copy this {@link Permutation} to a fresh target instance, then
* multiply each element by the argument using modulo N arithmetic.
* @param multiplier How much to multiply each member.
* @return The newly instantiated target instance.
*/
public Permutation multiply(int multiplier) {
int itemCount = itemCount();
if (MathMethods.gcd(multiplier, itemCount) != 1)
throw new IllegalArgumentException("Multiplier "
+ multiplier + " not relatively prime to member count " + itemCount);
Permutation target = new Permutation(null);
target.setItemCount(itemCount);
for (int position = 0; position < itemCount; position++) {
int member = members.memberAt(position);
member = MathMethods.modulo(member*multiplier, itemCount);
target.members.insertMember(member, position);
}
return target;
}
/**
* Populate the member array of the present {@link Permutation} instance with
* values derived from a source instance.
* This method leverages (@link iterateMembers()}, whose documentation further
* explains the start, increment, multiplier, and transposition arguments.
* @param source The source {@link Permutation} instance.
* @param start Starting position.
* @param increment Position increment between iterations.
* @param multiplier Multiplier applied modulo N to each member.
* @param transposition Offset added modulo N to each member.
*/
public void copyMembers(Permutation source,
int start, int increment, int multiplier, int transposition) {
setItemCount(source.itemCount());
Iterator<Integer> iterator = source.iterateMembers(start, increment, multiplier, transposition);
while (iterator.hasNext()) {
addMember(iterator.next());
}
}
/**
* Copy the members of the present {@link Permutation} into a newly
* allocated instance.
* @return A new {@link Permutation} instance with the same content.
*/
public Permutation copy() {
Permutation result = new Permutation(null);
result.copyMembers(this, 0, 1, 1, 0);
return result;
}
/**
* Get a text string listing the permutation elements.
* @return A text string listing the permutation elements.
*/
public String getText() {
int length = itemCount();
StringBuilder builder = new StringBuilder();
for (int position = 0; position < length; position++) {
if (0 < position) builder.append(' ');
builder.append(memberAt(position));
}
return builder.toString();
}
/**
* Shuffle the members into random order.
*/
public void shuffleMembers() {
itemCount();
members.shuffle();
}
/**
* Get the series value at the indicated index.
* @param index The position where the desired value lies.
* This index is wrapped into the range from 0 (inclusive) to the
* series length (exclusive) before the series value is dereferenced.
* @return The desired series value.
*
*/
public int memberAt(int index) {
int length = itemCount();
int position = MathMethods.modulo(index, length);
Integer member = members.memberAt(position);
if (Integer.MIN_VALUE == member)
throw new UninitializedException("Member not initialized at position " + position);
return member;
}
/**
* Test if this {@link Permutation} leaves each member in its original position.
* @return True when all members equal their own positions; false otherwise.
*/
public boolean isIdentity() {
int length = itemCount();
for (int position = 0; position < length; position++) {
if (memberAt(position) != position) return false;
}
return true;
}
/**
* Present the members of this permutation sequentially while applying configurable
* serial manipulations.
* @param start Starting position, which wraps into the range from 0 to length-1.
* Use start-value 0 for default forward sampling.
* Use start-value -1 for retrograde sampling (with increment -1) or left rotation
* by one position (with increment 1).
* Use start-value 1 for right rotation by one position (with increment 1).
* @param increment Position increment between iterations, which wraps
* into the range from 0 to length-1.
* Increment 1 produces default forward sampling.
* Increment -1 produces retrograde sampling.
* The increment argument must be relatively prime to the permutation length
* (zero does not qualify).
* @param multiplier Multiplies each iterated member.
* Multiplier 1 produces original member.
* Multiplier -1 inverts members around 0.
* The multiplier argument must be relatively prime to the permutation length
* (zero does not qualify).
* @param transposition Additive offset to each member, which wraps into the
* range from 0 to length-1.
* Use transposition 0 to
* @return An {@link Iterator} instance which in turn presents {@link Integer}
* member values.
* @throws IllegalArgumentException when the increment argument is not relatively
* prime to the permutation length.
* @throws IllegalArgumentException when the multiplier argument is not relatively
* prime to the permutation length.
*/
public Iterator<Integer> iterateMembers(
int start, int increment, int multiplier, int transposition) {
return new MemberIterator(start, increment, multiplier, transposition);
}
}
Listing 1: The
Permutation
implementation class.
/**
* The {@link IntArray} class wraps an integer array with a {@link Comparable#compareTo(Object)} operation.
* @author Charles Ames
*/
public class IntArray implements Comparable<IntArray> {
private Integer[] members;
/**
* Constructor for {@link IntArray} instances.
* @param length The array length.
*/
public IntArray(int length) {
this.members = new Integer[length];
}
/**
* Constructor for {@link IntArray} instances.
* @param values initialization array.
*/
public IntArray(Integer[] values) {
this(values.length);
for (int position = 0; position < values.length; position++) {
int value = values[position];
//System.out.println(value);
this.members[position] = value;
}
}
/**
* Get the count of members.
* @return The assigned count of members.
*/
public int itemCount() {
return members.length;
}
/**
* Insert the indicated value into the {@link #members} array at the indicated position.
* @param member The indicated value.
* @param position The indicated position.
*/
public void insertMember(int member, int position) {
members[position] = member;
}
/**
* Deference the indicated position of the {@link #members} array.
* @param position The indicated position.
* @return The member at the indicated position.
*/
public int memberAt(int position) {
return members[position];
}
/**
* Instantiate a new {@link IntArray} instance with the same content as this one.
* @return The new {@link IntArray} instance.
*/
public IntArray copy() {
return new IntArray(this.members);
}
// /**
// * Get the integer array.
// * @return The integer array, whose contents may be freely modified.
// */
// public int[] getArray() {
// return array;
// }
@Override
public int compareTo(IntArray other) {
Integer[] otherArray = other.members;
int length = members.length;
int otherLength = otherArray.length;
int minLength = Math.min(length, otherLength);
for (int i = 0; i < minLength; i++) {
int diff = members[i] - otherArray[i];
if (0 != diff) return diff;
}
return length - otherLength;
}
/**
* Shuffle the members into random order.
*/
public void shuffle() {
SharedRandomGenerator.shuffle(members);
}
/**
* Display this sequence of indices with the indicated offset.
* @param offset The indicated offset.
* @return A text string.
*/
public String toString(int offset) {
StringBuilder builder = new StringBuilder();
for (int position = 0; position < members.length; position++) {
if (position > 0) builder.append(' ');
builder.append(Integer.toString(members[position]+offset));
}
return builder.toString();
}
public String toString() {
return toString(0);
}
/**
* Convert a space-delimited string of integers to an {@link IntArray} instance.
* @param text A space-delimited string of integers.
* @return The newly-created {@link IntArray} instance.
*/
public static IntArray valueOf(String text) {
String[] tokens = text.split(" ");
IntArray value = new IntArray(tokens.length);
Integer[] array = value.members;
for (int position = 0; position < tokens.length; position++) {
try {
array[position] = Integer.valueOf(tokens[position]);
}
catch (Exception e) {
throw new RuntimeException(e.getMessage(), e);
}
}
return value;
}
/**
* Check if the indicated value already exists in the {@link #members} array.
* @param index The indicated value.
* @param limit Check up to, but not including, this position.
* @return The position where the value is found (Integer#MIN_VALUE if not
* found).
*/
public int positionOf(int index, int limit) {
if (limit < 0 || limit > members.length) throw new IllegalArgumentException("Limit out of range from 0 to " + members.length);
for (int position = 0; position < limit; position++) {
int member = members[position];
if (member == index) {
return position;
}
}
return Integer.MIN_VALUE;
}
/**
* Check if the indicated value already exists in the {@link #members} array.
* @param index The indicated value.
* @return The position where the value is found (Integer#MIN_VALUE if not
* found).
*/
public boolean contains(int index) {
for (int position = 0; position < members.length; position++) {
if (members[position] == index) {
return true;
}
}
return false;
}
}
Listing 2: The
IntArray
implementation class.
This closing section develops two Java classes implementing permutations
in different ways. The Permutation
class passively converts array-lookup indices from an original order to a permuted order. The
Sequence
class actively presents set elements in succession.
The Permutation
class provided as Listing 1 takes the basically passive approach of
converting array-lookup indices from an original order to a permuted order.
It holds its succession of indices in the IntArray
field
named members
.
The code for IntArray
is provided as Listing 2; it wraps functionality around an Integer
array. The implementation of interface Comparable<IntArray>
does not figure significantly in this present application; one feature that does figure is the copy()
method.
When constructing a permutation it is not sufficient to allocate it using
new Permutation()
.
The content must also be supplied. The most rudimentary way of doing this is first to establish the number of permutation members by calling
setItemCount(int)
, then to
populate members individually by calling
addMember(int member)
.
Each call to addMember()
places the new member in sequential order until
all positions are filled; it also checeks that that the member conforms to the permutation length and that the new member does not
duplicate a previous member.
The method fillAscending(int itemCount)
sizes the permutation to itemCount
then populates each member with its own position. This where to
start with if one intends to randomize the permutation order using the shuffle()
method.
If an Integer
array stores an already known permutation,
method setMembers(Integer[] members)
will
populate the succession into a Permutation
instance.
This method sizes the Permutation
to the source array and calls addMember()
on each array
element.
Individual succession members are accessible on a read-only basis using method
memberAt(int index)
. This simple array-element
getter implements the core functionality of the Permutation
class. That is, if you're working with a source
set containing N elements (not necessarily integers) and want to permute its elements, then the Permutation
instances you
want to work with should all be of length N, and the position k
in the original source order redirects to
memberAt(k)
in the permuted source order.
Method permute()
has three signatures for permuting the members of a target set in place:
-
If your source set exists as an
Object
array, method
permute(Object[] target)
will permute
these array elements in place.
-
If your source set exists as a
List<Object>
, method
permute(List<Object>
target) will permute
these List
items in place.
-
If your source set is itself a
Permutation
, method
permute(Permutation
target) will permute
its members in place.
The method iterateMembers(int start, int increment, int multiplier, int transposition)
returns an Iterator<Integer>
which presents the succession of
members in many familar variants.
From the returned Iterator
instance,
method next()
will return successive members until method
hasNext()
no longer returns true
.
Given a permutation length N, arguments outside the range from 0 to N-1 (e.g. -1) are wrapped back into range using
modular arithmetic.
The specific arguments are:
-
The
start
argument sets the starting value of the iterator's internal index — that is, it controls which member is presented first.
Each start
value applies a different rotation.
To obtain the unrotated sequence, set start
to 0.
-
The
increment
argument controls how far the index advances after each call to
Iterator.next()
.
Reference the above discussion of Every Nth.
This argument may not be zero, and it must be
relatively prime with the permutation length.
To obtain forward order, set increment
to 1.
To obtain reverse order, set increment
to -1.
-
The
multiplier
argument provides a modulo N multiplier.
Reference the above discussion of Multiplication.
This argument may not be zero, and it must be
relatively prime with the permutation length.
To disengage multiplication, set multiplier
to 1.
-
The
transposition
argument provides an offset which is added modulo N.
Reference the above discussion of Transposition.
So for example, iterateMembers(-1, -1, 1, 0)
will iterate through the permutation members in retrograde order.
If an existing source Permutation
stores an already known permutation, this can be specified using
method copyMembers(Permutation
source, int start, int increment, int multiplier, int transposition).
This method sizes the current Permutation
to the source Permutation
and
leverages source.iterateMembers()
to dereference the source content.
These methods create new Permutation instances and populate them:
-
Method
getCircleOfFifths()
returns a new Permutation
instance of length 12 where the kth member is k*7 mod 12.
Reference the above discussion of Multiplication.
-
Method
getOuterExchange(int itemCount)
returns a new Permutation
instance which takes each consecutive pair of members in the identity permutation and
exchanges their values. The itemCount)
argument must be even.
Reference the above discussion of Change Ringing.
-
Method
getInnerExchange(int itemCount)
returns a new Permutation
instance which starts with the identity permutation, leaves the initial and
final members alone, but exchanges the inner pairs (2&3, 4&5, etc.). The itemCount)
argument must be even.
Reference the above discussion of Change Ringing.
The following methods reorder the members of a Permutation
in place:
The following methods create new Permutation
instances which are derived from the method owner:
-
Method
invert()
creates a new Permutation
which is the mathematical inverse of the method owner.
Reference the above discussion of Inversion.
-
shiftRight(int increment)
creates a new Permutation
which is the mathematical inverse of the method owner.
Reference the above discussion of Rotation.
-
transpose(int offset)
Reference the above discussion of Transposition.
-
multiply(int multiplier)
Reference the above discussion of Multiplication.
/**
* Instances of the {@link Sequence} class iterate through
* a stored collection of values.
* @param <T> The type of output from {@link #next()}.
* Index sequences present {@link Integer} results.
* Driver sequences present {@link Double} results.
* @author Charles Ames
*/
public abstract class Sequence<T extends Number>
extends WriteableEntity {
/**
* Items in the {@link UsageMode} enumeration prescribe
* a {@link Sequence} instance's usage pattern.
* @author Charles Ames
*/
enum UsageMode {
/**
* No duplicates, no shuffling.
*/
UNIQUE_DIRECT("Stored values in strictly ascending order, no shuffling") {
@Override
void shuffleValues(Sequence<? extends Number> sequence) {
// Do nothing
}
},
/**
* No duplicates, no shuffling.
*/
UNIQUE_SHUFFLE("Stored values in strictly ascending order, with shuffling") {
},
/**
* Duplicates allowed, no shuffling.
*/
SAMPLES_DIRECT("Stored values in arbitrary order, no shuffling") {
@Override
void enforceUniqueness(Sequence<? extends Number> sequence, Number value) {
// Do nothing
}
@Override
void shuffleValues(Sequence<? extends Number> sequence) {
// Do nothing
}
},
/**
* Duplicates allowed, with shuffling.
*/
SAMPLES_SHUFFLE("Stored values in arbitrary order, with shuffling") {
@Override
void enforceUniqueness(Sequence<? extends Number> sequence, Number value) {
// Do nothing
}
};
/**
* Text description of this option, for option menu texts.
*/
private String text;
private UsageMode(String text) {
this.text = text;
}
/**
* Getter for {@link #text}.
* @return A text description of this option.
*/
public String getText() {
return text;
}
/**
* Identify a {@link UsageMode} instance from its description.
* @param text The {@link UsageMode} description.
* @return A {@link UsageMode} instance.
*/
public static UsageMode valueFromText(String text) {
for(UsageMode mode : UsageMode.values()) {
if (mode.text.equals(text)) return mode;
}
throw new IllegalArgumentException(
"There is no UsageMode with text [" + text + "]");
}
/**
* Require to-be-added value to be strictly greater than predecessor.
* @param sequence The {@link Sequence} to receive the new value.
* @param value The candidate value.
* @throws UnsupportedOperationException when new value
* is not strictly greater than predecessor and when not disengaged
* by override.
*/
void enforceUniqueness(Sequence<? extends Number> sequence, Number value) {
if (0 < sequence.values.size()) {
Number lastValue = sequence.values.get(sequence.values.size()-1);
if (sequence.compareValues(lastValue, value) > 0)
throw new UnsupportedOperationException(
"Non-ascending values not permitted in mode " + name());
}
}
/**
* Shuffle {@link Sequence#values} during call to {@link Sequence#reset()}.
* This default behavior can be disengaged by override.
* @param sequence The {@link Sequence} calling {@link Sequence#reset()}.
*/
void shuffleValues(Sequence<? extends Number> sequence) {
sequence.shuffleValues();
}
}
/**
* An ordered collection of values.
*/
private List<T> values;
/**
* The usage mode.
*/
private UsageMode mode;
private int position;
private int index;
/**
* After {@link #reset()}, first position from which to draw
* a value.
*/
private int samplingOffset;
/**
* Amount by which position is incremented after each call to
* {@link #generate()}.
*/
private int samplingIncrement;
/**
* Constructor for {@link Sequence} instances.
* @param container A {@link WriteableEntity} which contains
* this driver/indexer.
*/
public Sequence(WriteableEntity container) {
super(container);
setIDQuality(AttributeQuality.MODIFIABLE);
setNameQuality(AttributeQuality.MODIFIABLE);
this.values = new ArrayList<T>();
this.mode = null;
this.position = Integer.MIN_VALUE;
this.index = Integer.MIN_VALUE;
this.samplingOffset = Integer.MIN_VALUE;
this.samplingIncrement = Integer.MIN_VALUE;
}
/**
* Constructor for {@link Sequence} instances without container.
*/
public Sequence() {
this(null);
}
/**
* Getter for {@link #mode}.
* @return The assigned {@link #mode} value.
* @throws UninitializedException when the {@link #mode} has not been initialized.
*/
public UsageMode getMode() {
if (null == mode)
throw new UninitializedException("Usage mode not initialized");
return mode;
}
/**
* Setter for {@link #mode}.
* @param mode The intended {@link #mode} value.
*/
public void setMode(UsageMode mode) {
this.mode = mode;
}
/**
* Returns the number of elements in the {@link #values}
* collection.
* @return A non-negative integer.
*/
public final int itemCount() {
return values.size();
}
/**
* Getter for {@link #samplingOffset}.
* @return The assigned {@link #samplingOffset} value.
*/
public final int getSamplingOffset() {
if (Integer.MIN_VALUE == samplingOffset)
throw new UninitializedException("Sampling offset not initialized");
return samplingOffset;
}
/**
* Private setter for {@link #samplingOffset}.
* @param offset The intended {@link #samplingOffset} value.
* @return True if {@link #samplingOffset} has changed; false otherwise.
*/
private boolean setOffset(int offset) {
if (offset < 0)
throw new IllegalArgumentException("Negative offset");
if (this.samplingOffset != offset) {
this.samplingOffset = offset;
makeDirty();
return true;
}
return false;
}
/**
* Setter for {@link #samplingOffset}.
* @param samplingOffset The intended {@link #samplingOffset} value.
* @return True if {@link #samplingOffset} has changed; false otherwise.
*/
public final boolean setSamplingOffset(int samplingOffset) {
int itemCount = itemCount();
if (0 == itemCount)
throw new UnsupportedOperationException("No value array");
return setOffset(MathMethods.modulo(samplingOffset, itemCount));
}
/**
* Getter for {@link #samplingIncrement}.
* @return The assigned {@link #samplingIncrement} value.
*/
public final int getSamplingIncrement() {
if (Integer.MIN_VALUE == samplingIncrement)
throw new UninitializedException("Sampling increment not initialized");
return samplingIncrement;
}
/**
* Private setter for {@link #samplingIncrement}.
* @param increment The intended {@link #samplingIncrement} value.
* @return True if {@link #samplingIncrement} has changed; false otherwise.
*/
protected boolean setIncrement(int increment) {
if (increment < 0)
throw new IllegalArgumentException("Negative increment");
if (this.samplingIncrement != increment) {
this.samplingIncrement = increment;
makeDirty();
return true;
}
return false;
}
/**
* Setter for {@link #samplingIncrement}.
* @param samplingIncrement The intended {@link #samplingIncrement} value.
* @return True if {@link #samplingIncrement} has changed; false otherwise.
*/
public final boolean setSamplingIncrement(int samplingIncrement) {
int itemCount = itemCount();
if (0 == itemCount)
throw new UnsupportedOperationException("No value array");
int temp = MathMethods.modulo(samplingIncrement, itemCount);
if (MathMethods.gcd(temp, itemCount) != 1)
throw new IllegalArgumentException("Intended sampling increment "
+ temp + " not relatively prime to itemCount " + itemCount);
return setIncrement(temp);
}
/**
* Getter for {@link #values}.
* @return The {@link #values} collection
*/
protected List<T> getValues() {
return values;
}
/**
* Get the sample value from the indicated position in the
* {@link #values} collection.
* @param position The indicated position.
* @return The value in the indicated position.
* @throws UnsupportedOperationException when {@link #values}
* contains no elements.
*/
public T valueAt(int position) {
int itemCount = itemCount();
if (0 == itemCount)
throw new UnsupportedOperationException("No values populated");
if (0 > position || position >= itemCount)
throw new IllegalArgumentException(
"Position " + position + " outside range from 0 to " + (itemCount-1));
return values.get(position);
}
/**
* Return the next element in the {@link #values} collection.
* @return The a number between zero (inclusive) and unity (inclusive).
*/
public final T next() {
return generate();
}
protected T generate() {
int itemCount = itemCount();
if (index < 0 || index >= itemCount)
throw new UnsupportedOperationException("Iteration not in progress");
T result = valueAt(position);
position = MathMethods.modulo(position + getSamplingIncrement(), itemCount);
index++;
return result;
}
/**
* Test if the if the {@link #values} collection still contains unpresented
* values
* @return true if the sequence from {@link #values} contains unpresented
* values; false if the sequence is complete.
* @throws UnsupportedOperationException when iteration from
* {@link #values} is not in progress.
*/
public boolean hasNext() {
return index >= 0 && index < itemCount();
}
/**
* Append a new element to the {@link #values} collection.
* @param value The indicated value element.
* @throws UnsupportedOperationException when iteration
* from {@link #values} is in progress.
*/
public void addValue(T value) {
if (hasNext())
throw new UnsupportedOperationException("Iteration in progress");
getMode().enforceUniqueness(this, value);
checkValue(value);
values.add(value);
}
/**
* Append an array of elements to the {@link #values} collection.
* @param source The value array.
* @throws UnsupportedOperationException when {@link #values}
* already contains elements.
* @throws UnsupportedOperationException when iteration from
* {@link #values} is in progress.
*/
public void fillValues(T source[]) {
if (0 != itemCount())
throw new UnsupportedOperationException("Values already populated");
for (T value : source) {
addValue(value);
}
}
/**
* Append a collection of elements to the {@link #values} collection.
* @param source The value collection.
* @throws UnsupportedOperationException when {@link #values}
* already contains elements.
* @throws UnsupportedOperationException when iteration from
* {@link #values} is in progress.
*/
public void fillValues(Collection<T> source) {
if (0 != itemCount())
throw new UnsupportedOperationException("Values already populated");
for (T value : source) {
addValue(value);
}
}
/**
* Fill the {@link #values} collection with {@code length} values which
* are evenly spaced between zero and unity.
* @param length The intended size of the {@link #values} collection.
* @throws IllegalArgumentException when the length argument
* is not positive.
* @throws UnsupportedOperationException when {@link #values}
* already contains elements.
* @throws UnsupportedOperationException when iteration from
* {@link #values} is in progress.
*/
public abstract void fillAscending(int length);
/**
* Shuffle the contents of the {@link #values} collection. This method is
* normally used in conjunction with {@link #fillAscending(int)}.
* @throws UnsupportedOperationException when {@link #values}
* contains no elements.
* @throws UnsupportedOperationException when iteration from
* {@link #values} is in progress.
*/
public final void shuffleValues() {
if (0 == itemCount())
throw new UnsupportedOperationException("No values populated");
if (hasNext())
throw new UnsupportedOperationException("Iterator in progress");
SharedRandomGenerator.shuffle(values);
}
/**
* Permute the contents of the {@link #values} collection. This method is
* normally used in conjunction with {@link #fillAscending(int)}.
* @param permutation The revised order for {@link #values}.
* @throws IllegalArgumentException when the permutation length is
* inconsistent with {@link #values}.
* @throws UnsupportedOperationException when {@link #values}
* contains no elements.
* @throws UnsupportedOperationException when iteration from
* {@link #values} is in progress.
*/
public final void permuteValues(Permutation permutation) {
int length = itemCount();
if (0 == length)
throw new UnsupportedOperationException("No values populated");
if (permutation.itemCount() != length)
throw new IllegalArgumentException("Incompatible permutation");
if (hasNext())
throw new UnsupportedOperationException("Iterator in progress");
List<T> scratch = new ArrayList<T>();
for (int position = 0; position < length; position++)
scratch.add(values.get(position));
for (int position = 0; position < length; position++)
values.set(permutation.memberAt(position), scratch.get(position));
}
/**
* Query if this driver/indexer class supports the {@link #reset()} operation.
* @return true if {@link #reset()} is supported; false otherwise.
*/
public final boolean hasReset() {return true;}
/**
* Reset iteration through the {@link #values} collection so that the next
* call to {@link #next()} draws from the collection at starting
* position {@link #samplingOffset}.
*/
public final void reset() {
itemCount();
getMode().shuffleValues(this);
index = 0;
position = 0;
}
/**
* Empty the {@link #values} collection of all content.
*/
public final void clear() {
values.clear();
}
/**
* Verify value is in range.
* @param value Something about to be appended to the {@link #values} collection.
*/
protected abstract void checkValue(T value);
/**
* Compare two values.
* @param a First value.
* @param b Second value.
* @return 1 if a>b, -1 if a<b, 0 otherwise.
*/
protected abstract int compareValues(Number a, Number b);
}
Listing 3: The
Sequence
base class.
The abstract Sequence
class presented as Listing 3
implements common functionality for a family of units which maintain a collection of elements and which, upon request,
actively presents these elements in succession. The mechanism for presenting elements employs the
hasNext()/next()
design
of java.lang.Iterator, which presents
successive elements without recourse to an explicit lookup index.
The first thing to notice in Listing 3 is the generic parameter T
which
extends java.lang.Number
.
Number
is an abstract base class whose implementing sub-classes include
Integer
and
Double
.
In practice, T
can be either of these. Sequence
has two concrete subclasses.
IndexSequence
extends
Sequence<Integer>
; this supports
the Index/Supply pattern for sequence generation.
DriverSequence
extends
Sequence<Double>
; this supports
the Driver/Transform pattern for sequence generation.
My Sequence
class is named after the most fundamental of "selection principles"
in Gottfried Michael Koenig's Project2 composing program. Koenig's "Sequence"
simply iterated through supply elements in their original order; the present implementation also supports iterating
through a supply in random order (what Project2 's "Series" selection principle did), or in permuted order.
Understand that the values
collection embedded into my
Sequence
implementation does not correspond to what
Koenig called the "supply". Rather, for IndexSequence
the values
collection can be regarded as a set of supply-selection
indices.
The life cycle of a Sequence
instance has three phases:
Construction, Population, and Consumption:
-
Construction allocates the instance
using the
new
operator.
-
Population brings values into
the embedded collection of
T
elements named
values
.
During this phase, successive calls to addValue()
append
additional T
elements to the collection.
When the mode
is UsageMode.UNIQUE_DIRECT
or UsageMode.UNIQUE_SHUFFLE
, each additional T
element
must be strictly greater than its predecessor. Among other things this prevents duplicate T
elements.
-
Consumption happens in cycles. Each cycle begins with a call to
reset()
. This call begins a preparation
stage which establishes specific features of the cycle. Then follows an iteration stage.
Iteration begins with the first pair of calls to hasNext()
,
and — if hasNext()
returns true
—
to next()
. Iteration continues until
hasNext()
returns false
.
When the mode
is UsageMode.UNIQUE_SHUFFLE
or UsageMode.SAMPLES_SHUFFLE
, each call
to reset()
provokes a call to shuffleValues()
.
Once consumption has commenced, it is bad practice to make further calls to addValue()
without first calling clear()
. The clear()
method empties out the values
collection, establishing a clean slate.
These methods assist in the Population phase:
-
Method
fillValues(T source[])
populates the values
collection from an array.
-
Method
fillValues(List<T> source[])
populates the values
collection from a
java.util.List
.
-
Method
fillAscending(int itemCount)
varies
with the concrete implementation class. For IndexSequence
,
fillAscending()
populates values
with the integers from 0
to itemCount-1
. For DriverSequence
,
fillAscending()
populates values
with
itemCount
double-precision values which are spaced evenly between zero and unity.
These methods assist in the preparation stage of the Consumption phase:
-
Method
setSamplingOffset(int samplingOffset)
sets the starting value of the internal iteration index — that is, it controls which member is presented first.
Each samplingOffset
value applies a different rotation.
To obtain the unrotated sequence, set samplingOffset
to 0.
-
Method
setSamplingIncrement(int samplingIncrement)
controls how far the internal iteration index advances after each call to
next()
.
Reference the above discussion of Every Nth.
This argument may not be zero, and it must be
relatively prime with the length of values
.
To obtain forward order, set samplingIncrement
to 1.
To obtain reverse order, set samplingIncrement
to -1; also set samplingOffset
to -1.
-
Method
shuffleValues()
shuffles the elements of values
randomly.
This method makes sense only in conjunction with fillAscending()
, with a
samplingOffset
of 0, and with a samplingIncrement
of 1.
-
Method
permuteValues(Permutation permutation)
reorders the elements of values
as directed by permutation
.
This method makes sense only in conjunction with fillAscending()
, with a
samplingOffset
of 0, and with a samplingIncrement
of 1.
The mode
field and the various UsageMode
options have differing implications depending on whether the stored values are lookup indices
(IndexSequence
) or statistical drivers
(DriverSequence
). Here I just want to draw
attention to the enforceUniqueness()
and shuffleValues()
methods associated with the UsageMode
enumeration items. These methods allow me to
eliminate switch
clauses branching off the usage mode. I not knowledgeable about the
relative computational efficiency of enumeration-method calls versus switch
clauses; however
switch
clauses are definitely bad from a maintenance perspective: each time a new enumeration
option is added, every affected switch
clause also needs revising.
-
The present text is partially adapted from my Leonardo Music Journal
article from 1992, "A Catalog of Sequence Generators". The heading is
"Dependence", p. 55.
-
Herstein, I.N., Topics in Algebra 2nd Ed., Lexington MA: Xerox College Publishing, 1975.
-
According to Claudio Spies in "Some Notes on Stravinsky's Requiem Settings", Perspectives of New Music
Vol. 5 No. 2 (1967) pp. 98-123.
© Charles Ames |
Page created: 2022-08-29 |
Last updated: 2022-08-29 |