By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,730 Members | 1,559 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,730 IT Pros & Developers. It's quick & easy.

permutations, patterns, and probability

P: n/a
Greetings,

I am working on a program to produce patterns. What would like is for
it to exhaustively produce all possible permutations of a sequence of
items but for each permutation produce variations, and also a sort of
stutter based on probability / weighted randomess.

Let us say we have tiles of four primary colors: ['Red', 'Blue',
'Green', 'Yellow']. Now we also have 4 alternatives or substitutes for
each color ['Maroon', 'Navy_Blue', 'Forest_Green', 'Dark_Brown']

We pick a unique permutation, say: ['Red', 'Blue', 'Yellow', 'Green']

Now I would like to pick the primary colors substitute (say 30% chance
for each element) so instead of our plain

['Red', 'Blue', 'Yellow', 'Green']

we might end up with:

['Red', 'Navy_Blue', 'Yellow', 'Forest_Green']

or

['Maroon', 'Navy_Blue', 'Yellow', 'Green']

Whatever... The main point is that sometimes the original color is
retained and sometimes the dark color is substituted.

Now I want to take this list and sometimes stutter an element so that
there is, let us say a 50% chance for each element, that it is
stuttered, and it may be repeated 1 (34%), 2(66%), or 3(33%) times. So
that we could get:

['Maroon','Maroon','Navy_Blue', 'Yellow','Yellow','Yellow','Yellow',
'Green']

The program would quit when all 24 (in the case of 4 elements) was
exhausted.

I have code that makes weighted randomness. I have code that makes
permutations, but I am having trouble putting this all together...
While i work on it though that i might ask for help... I'd like for the
code to be reusable and am building a library of functions for
patterns.

cheers,
kevin
### This is not mine, it is from a python book... I believe the Lutz
book

def permute(list):
if not list: # shuffle any
sequence
return[list] # empty
sequence
else:
res = []
for i in range(len(list)):
rest = list[:i] + list[i+1:] # delete
current node
for x in permute(rest): # permute the
others
res.append(list[i:i+1] + x) # add node at
front
return res

mport random

### This this is mine, but seems to work anyway hee hee

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
like: >>> x = [('one', 0.25), ('two', 0.25), ('three', 0.5)]
y=windex(x)'''

n = random.uniform(0, 1)
for item, weight in lst:
if n < weight:
break
n = n - weight
return item

Jul 18 '05 #1
Share this Question
Share on Google+
1 Reply


P: n/a
kpp9c wrote:
Greetings,

I am working on a program to produce patterns. What would like is for
it to exhaustively produce all possible permutations of a sequence of
items but for each permutation produce variations, and also a sort of
stutter based on probability / weighted randomess.

Let us say we have tiles of four primary colors: ['Red', 'Blue',
'Green', 'Yellow']. Now we also have 4 alternatives or substitutes for
each color ['Maroon', 'Navy_Blue', 'Forest_Green', 'Dark_Brown']

We pick a unique permutation, say: ['Red', 'Blue', 'Yellow', 'Green']

Now I would like to pick the primary colors substitute (say 30% chance
for each element) so instead of our plain

['Red', 'Blue', 'Yellow', 'Green']

we might end up with:

['Red', 'Navy_Blue', 'Yellow', 'Forest_Green']

or

['Maroon', 'Navy_Blue', 'Yellow', 'Green']

Whatever... The main point is that sometimes the original color is
retained and sometimes the dark color is substituted.

Now I want to take this list and sometimes stutter an element so that
there is, let us say a 50% chance for each element, that it is
stuttered, and it may be repeated 1 (34%), 2(66%), or 3(33%) times. So
that we could get:

['Maroon','Maroon','Navy_Blue', 'Yellow','Yellow','Yellow','Yellow',
'Green']

The program would quit when all 24 (in the case of 4 elements) was
exhausted.


Playing around with this:

py> def alt_color(color, color_map=dict(Red='Maroon',
.... Blue='Navy_Blue',
.... Yellow='Forest_Green',
.... Green='Dark_Brown')):
.... if random.random() <= 0.3:
.... return color_map[color]
.... return color
....
py> def reps():
.... if random.random() < 0.5:
.... return 1
.... return random.randint(2, 4)
....
py> def combinations(items, n):
.... if n==0:
.... yield []
.... else:
.... for i in xrange(len(items)):
.... item_slice = items[i:i+1]
.... for c in combinations(items[:i]+items[i+1:], n-1):
.... yield item_slice + c
....
py> colors = ['Red', 'Blue', 'Yellow', 'Green']
py> some_colors = combinations(colors, len(colors)).next()
py> some_colors
['Red', 'Blue', 'Yellow', 'Green']
py> alt_colors = [alt_color(c) for c in some_colors]
py> alt_colors
['Red', 'Navy_Blue', 'Yellow', 'Green']
py> rep_colors = [c for color in alt_colors for c in [color]*reps()]
py> rep_colors
['Red', 'Red', 'Navy_Blue', 'Navy_Blue', 'Navy_Blue', 'Yellow', 'Green',
'Green']

Hope some of that is helpful.

Steve
Jul 18 '05 #2

This discussion thread is closed

Replies have been disabled for this discussion.