Basics III: Permutation1

Overview

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.

Introduction

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:

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.

Categories of Permutation

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.

Identity

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.

Retrograde

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.

Every Nth

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

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:

01234567891011
12345678910110
23456789101101
34567891011012
45678910110123
56789101101234
67891011012345
78910110123456
89101101234567
91011012345678
10110123456789
11012345678910

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

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):

01234567891011
05103816114927
07294116183105
01110987654321

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

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:

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

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:

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.

Random Shuffling

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.

Inverse Permutations

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):

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}:

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.

Coding

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

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:

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:

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:

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:

/**
 * 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 Sequence 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:

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:

These methods assist in the preparation stage of the Consumption phase:

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.

  1. 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.
  2. Herstein, I.N., Topics in Algebra 2nd Ed., Lexington MA: Xerox College Publishing, 1975.
  3. 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