[Tutor] permutations, patterns, and probability

kevin parks kp8 at mac.com
Wed Feb 2 00:53:13 CET 2005


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']


['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', 

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

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 


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

def permute(list):
     if not list:                                        # shuffle any 
         return [list]                                   # empty sequence
         res = []
         for i in range(len(list)):
             rest = list[:i] + list[i+1:]                # delete 
current node
             for x in permute(rest):                     # permute the 
                 res.append(list[i:i+1] + x)             # add node at 
         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:
                 n = n - weight
         return item

More information about the Tutor mailing list