[EMAIL PROTECTED] wrote:
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())


-- 
http://mail.python.org/mailman/listinfo/python-list

Reply via email to