[Tutor] permutations, patterns, and probability

Kent Johnson kent37 at tds.net
Wed Feb 2 02:43:52 CET 2005


kevin parks 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.
> 
> 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.

If you had a randomizeList function and a stutterList function then your top-level function would 
look like this:

permutations = permute(['Red', 'Blue', 'Yellow', 'Green'])
permutations = [ randomizeList(list) for list in permutations ]
permutations = [ stutterList(list) for list in permutations ]

In other words you start with the basic permutations, then apply the randomize function to each 
permutation, then apply the stutter function.

The randomizeList function should walk through the list, find the right randomize list for that list 
element (a dict could help with that - look up the list element and get the randomize list), and 
build a new list with the randomized values.

The stutterList function walks through the list building a new list with possibly repeated elements.

HTH,
Kent

> 
> 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
> 
> 
> 
> 
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
> 



More information about the Tutor mailing list