I want to use it for music. So given list 1 (melody), list 2 (chords)
could be generated by a Markov chain. Also, given the chords the melody
could be generated again by a chain.
I have this small module, that can be used for markov chains.
--
hilsen/regards Max M, Denmark
http://www.mxm.dk/
IT's Mad Science
from random import random, randint
from bisect import bisect
class Randomizer:
"Various stochastic methods"
def inverse_scale(self, rng):
"Returns a list of probablitites corresponding to 1/i in range"
return [1.0 / (i + 1.0) for i in range(rng)]
def n_scale(self, rng, n=2.0):
"Returns a list of probablitites corresponding to i/n"
n_scale = []
value = 1.0
for i in range(rng):
value /= n
n_scale.append(value)
return n_scale
class Selector:
"Returns random elements by probability according to their frequency"
def __init__(self, frequencies, elements):
self.sum = sum(frequencies)
acumulated_frequencies = []
acumulated_frequency = 0
for frequency in frequencies:
acumulated_frequency += frequency
acumulated_frequencies.append(acumulated_frequency)
self.decorated = zip(acumulated_frequencies, elements)
self.decorated.sort()
def get(self):
"Randomly returns an element by probability"
rnd = random() * self.sum
index = bisect(self.decorated, (rnd, 0))
return self.decorated[index][-1]
def get_range(self, n):
"Randomly returns a range of elements by probability"
return [self.get() for itm in xrange(n)]
class MarkovIn:
"""
Implements a Markov chain for arbitrary objects. The objects has
same rules as dictionary keys to be valid.
"""
def __init__(self, key_size=1):
"""
key_size: how many steps in the chain
"""
self.key_size = key_size
self.in_history = []
self.chain = {}
def _update_chain(self, obj):
"Puts the object into the chain"
# shortcuts
ch = self.chain
# update the chain
key = tuple(self.in_history)
stat = ch.setdefault(key, {})
ch[key][obj] = stat.setdefault(obj, 0) + 1
def _update_history(self, obj):
"Updates the history"
his = self.in_history
his.append(obj)
if len(his) > self.key_size:
his.pop(0)
def add_object(self, obj):
"Adds an object to the chain"
self._update_chain(obj)
self._update_history(obj)
def reset(self):
"Resets the history"
self.in_history = []
class MarkovOut:
"""
A Markov Chain wrapper.
Generates a "random walk" from a markov chain.
It is a seperate object for performance reasons.
"""
def __init__(self, markov):
"""
markov: A populated MarkovIn object
"""
self.markov = markov
self.key_size = markov.key_size
self.out_history = []
# Set up a cache of selector objects
selectors = {}
ch = self.markov.chain
for key in ch.keys():
m = ch[key]
selectors[key] = Selector(m.values(), m.keys())
self.selectors = selectors
def _update_history(self, obj):
"Updates the history"
his = self.out_history
his.append(obj)
if len(his) > self.key_size:
his.pop(0)
def step(self):
"A 'random' step from the chain, returns an object"
his = self.out_history
key = tuple(his)
obj = self.selectors[key].get()
# keep track of history
self._update_history(obj)
new_key = tuple(his)
self.handle_step(obj)
if not self.selectors.has_key(new_key):
# reset history and start over
self.out_history = []
self.restart()
def handle_step(self, obj):
"Handles a single step"
self.steps.append(obj)
def do_walk(self, steps=1):
"returns A 'probable' walk"
self.steps = []
for itm in xrange(steps):
self.step()
def get_walk(self):
"Returns the walk"
return self.steps
def _reset(self):
"Resets the history"
self.out_history = []
def restart(self):
"A hook for when a walk restarts"
pass
if __name__ == '__main__':
f = open('input.txt')
text = f.read()
lines = text.split('\n')
mi = MarkovIn(1)
for line in lines:
mi.reset()
words = line.split()
for word in words:
mi.add_object(word)
class mo(MarkovOut):
def __init__(self, markov_out):
MarkovOut.__init__(self, markov_out)
def restart(self):
self.steps.append('\n\n')
m = mo(mi)
m.do_walk(100)
print ' '.join(m.get_walk())
).