J
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 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
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 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