Fundamental Patterns

by Chris Korda

It's well-known that the number of permutations for a set of size N is N factorial. We will show that most of these permutations are transformations of a much smaller subset of patterns called prime forms. For N=4 there are 24 permutations, but only three prime forms, and they are:

Each of these prime forms has eight transformations, as shown below: four by cyclic rotation, and another four by cyclic rotation of the reversed pattern.

Thus 24 permutations are reduced to a mere three patterns. The number of prime forms M for a set of size N is given by N! / (N × 2).

A method for obtaining the prime forms for a given set size N is described below.

The method requires a hashing function that converts every permutation of the set to a unique integer. The function interprets the permutation as a base N number and tightly packs its digits. More succinctly, the function sums D_i×N^(N−i−1) for i=[0..N−1]. For example the set [1 0 3 2] is hashed to the value 78:

1×4³+0×4²+3×4¹+2×4⁰ = 1×64×0×16+3×4+2×1 = 64+0+12+2 = 78

Using this hashing function, we can convert any given permutation of the set to its prime form. This is done by generating all the rotations and reversed rotations and hashing each of them. The transformation that produces the smallest hash is the prime form.

Now iterate through all the permutations of the given set. For each permutation, convert it to its prime form, and if that prime form hasn’t been encountered before, add it to a list. At the end of the iteration, the list contains all of the prime forms for a set of size N.

A prime form pattern can be conceptualized as a series of N intervals which generate the values [0..N−1] in a characteristic sequence. To obtain the intervals, compute the absolute difference between each pair of adjacent elements. For example, here are the prime forms and their intervals for N=4:

The vector column above is analogous to the interval vector used in musical set theory. It’s read from left to right. The leftmost element is the count of steps of size one, the next element is the count of steps of size two, and so on. The pattern [0 1 2 3] contains three steps of size one, no steps of size two, and a single step of size three, hence its interval vector is <301>. All of the transformations of a prime form have the same interval vector.

The twelve prime forms for N=5 along with their interval vectors are shown below. Multiple prime forms can share the same interval vector, and in such cases the prime forms are related.