kevin parks wrote:
<div class="moz-text-flowed" style="font-family: -moz-fixed">I posted
about this a couple weeks back, but then got horribly ill and dropped
the ball so i was hoping to revisit.
I am not sure if this is and example of Finite Automaton or a Finite
State Machine or perhaps it is related to a transition table or markov
process. I think some one here told me it is called a transitional
grammar? I am not sure. I am not a math person but i would love to
know exactly what this is. I googled around and got lots of super
complicated gobbledegoo all with knotty regex stuff, but what i want
to do is much more simple. I am trying to use a table to define a
bunch of moves like so:
1 --> 2 5
2 --> 1 4
3 --> 3
4 --> 1
5 --> 4 3
so that i can generate a sequence that, given an initial value, that
will continue to grow according to these rules. Starting with 1 we
then go to 2 & 5, 2 leads us too 1 & 4, the 5 leads us to 4 & 3, then
we iterate over 1 4 4 and 3 to get 2 5 1 1 and 3.... Like so:
1
2 5
1 4 4 3
2 5 1 1 3
1 4 4 3 2 5 2 5 3
..... etc.
Essentially, iterating over the last added items to the list, applying
the table, appending those new items to the list, applying the table
again... etc, until the sequence reaches some predetermined number of
iterations and quits.
[ [1], [2, 5], [1, 4] , [4, 3], [2, 5], [1], [1], [3], [1, 4], [4, 3],
[2, 5], [2, 5], [3] ]
First, as i mentioned I would like to know what, precisely, this kind
of process is called so that i can look it up. Second, i would l like
to add to what i have, which seems to work. But first here is the
code, where we left off below:
#!/usr/bin/env python
rules = {1: (2, 5), 2: (1, 4), 3: (3,), 4: (1,), 5: (4, 3)}
def apply_rules(sequence):
for element in sequence:
# look it up in the global rules
values = rules[element]
# yield each of those in turn
for value in values:
yield value
def flatten(l, ltypes=(list, tuple)):
ltype = type(l)
l = list(l)
i = 0
while i < len(l):
while isinstance(l[i], ltypes):
if not l[i]:
l.pop(i)
i -= 1
break
else:
l[i:i + 1] = l[i]
i += 1
return ltype(l)
def test():
data = [1]
outlist = []
for i in range(10):
outlist.append(data)
gen = apply_rules(data)
data = list(gen)
outlist.append(data) # one more to get the final result
print '\n\n', outlist, '\n\n'
flat = flatten(outlist)
count = 0
for item in flat:
print count, ',', item, ';'
count += 1
print '\n\n'
if __name__ == "__main__":
test()
This all appears to work. I am not sure if this is the best way to do
it, but for the size lists i have been generating it seems zippy.
So what? You are asking a question you already know the answer to?
Well now I would like to have this set of rules contain some
probabilistic branching. Instead of having my "go to" rules or grammar
hard wired it would be good if some steps could also have weighted
choices. So that maybe 1 --> 2 5 70% of the time but maybe it goes 1
--> 2 4 every once in a while (as in 30%). So i am not sure how to do
that... also, it occurs to me that i could define a grammar that got
stuck in an infinite loop if not careful. I wonder if i should add
some mechanism to check the dictionary defined rules before
execution.... or if that is just too hard to do and i should just be
careful.
Meanwhile I have my trusty old weighted random func all ready to go:
import random
def windex(lst):
'''an attempt to make a random.choose() function that makes
weighted choices
accepts a list of tuples with the item and probability as a pair'''
wtotal = sum([x[1] for x in lst])
n = random.uniform(0, wtotal)
for item, weight in lst:
if n < weight:
break
n = n - weight
return item
My question is how to apply this since i am setting up my rules in a
dictionary, so I am confused as to how all these pieces, which work in
isolation, would fit together. Lastly, if i add the probabilities...
is this just a super roundabout way to make a quasi markov table? i
dunno. But it seems like a cool way to make patterns.
</div>
Often, when a combination of existing stdlib collection types gets too
confusing, it's time to consider classes and objects. Not necessarily
to make the program "object oriented," but to make the program data
structure understandable.
You have a dictionary mapping from ints to tuples of ints. You want to
keep the same dictionary keys, but make the values more complex. Each
value, instead of being a tuple, needs to be a list of tuples, with a
probability assigned to each.
So create a class for that "list of tuples," and modify windex to work
on an object of such a class. And in apply_rules, change the values=
line to call windex() after doing the lookup.
I don't see where an infinite loop is possible. But it'd be useful to
do some error checking for the class items, such as validating that the
probabilities add up to 100% (within a tolerance factor).
DaveA
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
