Algorithm for generating pitch-class sets in prime form

[John O'Hagan]

I'm looking for some help coming up with an algorithm to produce lists which 
meet the following criterion (you don't need to know music to get this):

In musical pitch-class set theory, "prime form" is defined as the most tightly-
packed-to-the-left rotation of a set's interval structure. Prime forms are 
important in music because they provide the unique simplest form of any pitch 
structure. I'm writing a python program which uses this principle.

For example: the sequence [2, 6, 9] (which happens to be a D major chord) 
would be put in prime form by:

- Sorting and transposing it so it starts on zero: [0, 4, 7]
- Expressing it as intervals: [4, 3, 5] (the last number is the distance to 
the octave)
- Rotating the intervals such that the biggest interval is at the end; if 
there are more than one biggest intervals, we want the rotation with the 
smallest first interval, and if that is also tied, the one with the smallest 
second interval, and so on. In this example we are already there. 

An easy way of finding a prime form in Python is:

def prime_form(seq):
    pcs = sorted(list(set(seq)))
    intervals = ([pcs[i + 1] - pcs[i] for i in range(len(pcs) - 1)] + 		
		[12 + min(pcs) - pcs[-1]])
    rotations = [intervals[i:] + intervals[:i] for i in range(len(intervals))]
    prime_intervals = min([i for i in rotations if i[-1] == max(intervals)])
    return [sum(prime_intervals[:i]) for i in range(len(prime_intervals))]
    
But I'm looking for a way of generating sequences already in prime form 
without duplication or omission. One promising approach is using a function 
which generates all the (ordered) partitions of a number, and producing the 
multiset permutations of each partition, which gives us all the possible 
interval structures (but many of which are rotationally equivalent):

def full(num):
    for part in partitions(num):
        for perm in multiset_permutations(part):
            yield perm

(The actual functions I'm using for this are at the end of this message.)

To start narrowing it down to prime forms, we can chop off the largest interval 
from the end, permute the rest, and replace it on the end of each permutation:

def full(num):
    for part in partitions(num):
        if len(part) == 1:
            yield part
        else:
            for perm in multiset_permutations(part[:-1]):
                yield perm + part[-1]

but this produces a lot of false positives in cases where there is more than 
one largest interval.

I imagine a solution might work by removing the largest intervals from each 
partition, permuting the remaining intervals, and into each permutation 
inserting the large intervals, one at the end and the others in each possible 
place that satisfies the requirements. And that's where I'm getting lost.

Any clues, suggestions or solutions?

Regards,

John


The functions:

def partitions(num):
    if  num == 0:
        yield []
        return
    for part in partitions(num-1):
        yield [1] + part
        if part and (len(part) < 2 or part[1] > part[0]):
            yield [part[0] + 1] + part[1:]

def _reverse(seq, start, end):
    "A sub-function for multiset_permutations"
    #seq = seq[:start] + reversed(seq[start:end]) + seq[end:]
    end -= 1
    if end <= start:
        return
    while True:
        seq[start], seq[end] = seq[end], seq[start]
        if start == end or start+1 == end:
            return
        start += 1
        end -= 1

def multiset_permutations(seq):
    first = 0
    last = len(seq)
    yield seq
    if last == 1:
        raise StopIteration
    while True:
        next = last - 1
        while True:
            next1 = next
            next -= 1
            if seq[next] < seq[next1]:
                mid = last - 1
                while seq[next] >= seq[mid]:
                    mid -= 1
                seq[next], seq[mid] = seq[mid], seq[next]
                _reverse(seq, next1, last)
                yield seq
                break
            if next == first:
                raise StopIteration
    raise StopIteration