[Tutor] Automatic generation of an "all possible combinations" array

[Hugh M]

Ah, in the case of looking for all n-digit bit-strings that contain exactly
m-1's, the recursive solution is even nicer.  Here's how I think of it:
Base Case(s):
- if you want 0 1's (m==0) then return all 0's.
- if you want all 1's (n==m) then return all 1's.

Otherwise Recursive Case:
- return the set of all (n-1)digit bit-strings that contain exactly m-1's
plus a 0
combined with the set of all (n-1)digit bit-strings that contain exactly
m-1's plus a 1

Here's some code that does just that:

def recursive_bit_list(n,m):
    if m==0:
        return [n*[0]]
    elif n==m:
        return [n*[1]]
    else:
        return map(lambda x: x+[0], recursive_bit_list(n-1,m)) + \
               map(lambda x: x+[1], recursive_bit_list(n-1,m-1))


If you want it faster and don't mind building up a large in-memory
dictionary as you compute this, you can try incorporating a "memoizer" so
that you don't repeatedly compute the same answer many times.

e.g.:

memoizer = {}

def recursive_bit_list(n,m):
    global memoizer
    if memoizer.has_key((n,m)):
        return memoizer[(n,m)]
    elif m==0:
        return [n*[0]]
    elif n==m:
        return [n*[1]]
    else:
        answer = map(lambda x: x+[0], recursive_bit_list(n-1,m)) + \
               map(lambda x: x+[1], recursive_bit_list(n-1,m-1))
        memoizer[(n,m)] = answer
        return answer


I didn't do any extensive tests- when n is large both of these are far from
speedy...  Maybe there are other ideas?

Good luck!

-Hugh



On 6/15/07, Andy Cheesman <Andy.cheesman at bristol.ac.uk> wrote:
>
> The code works great, Thanks for the speedy response. The only problem
> which I can see is that the code scales very bad with the size of n.
>
> So, as  I want a small subsection of the data (i.e lines where there are
> only 4 1s, number in the code below) for a system where n is large(>20).
> The idea is that this  would reduce the number of iterations dramatic
> despite the individual loop taking longer to operate.(see example data).
> I've modified the bit_list_maker to allow for this but it has started to
> produce rows which are identical.
> Can anyone make any suggestion/improvements to the code
>
> def bit_list_maker_mod(n, number):
>     x = n*number
>     solution_set = []
>     row_total = number
>     for i in range(x):
>         this_answer = []
>         row = 0
>         while i>0:
>             this_answer.append(i%2)
>             if i%2 == 1:
>                 row +=1
>             i=i/2
>             if row == row_total:
>                 break
>         while len(this_answer)<n:
>             this_answer.append(0)
>         this_answer.reverse()
>         solution_set.append(this_answer)
>     return solution_set
>
> Hugh M wrote:
> > The 2**n different lists that you are seeking have a direct association
> > to the binary representation of the integers 0 through (2**n)-1.
> >
> > You can use this fact and the "repeated division method" for converting
> > numbers between different bases to generate these lists and form the
> > desired list of lists:
> >
> > def bit_list_maker(n):
> >     x = 2**n
> >     solution_set = []
> >     for i in range(x):
> >         this_answer = []
> >         while i>0:
> >             this_answer.append(i%2)
> >             i=i/2
> >         while len(this_answer)<n:
> >             this_answer.append(0)
> >         this_answer.reverse()
> >         solution_set.append(this_answer)
> >     return solution_set
> > *
> > *
> > Another fun way to do it is to build up the lists recursively.  The
> > possibilities for n bits can be built from the possibilities for n-1
> > bits by adding a 1 and a 0 to each possibility (ending up with twice as
> > many elements):
> >
> > def recursive_bit_list(n):
> >     if n==1:
> >         return [[0],[1]]
> >     else:
> >         return map(lambda x: x+[0], recursive_bit_list(n-1)) + \
> >                map(lambda x: x+[1], recursive_bit_list(n-1))
> >
> > Hope this helps!
> >
> > -Hugh
> >
> >
> > On 6/14/07, *Andy Cheesman* <Andy.cheesman at bristol.ac.uk
> > <mailto: Andy.cheesman at bristol.ac.uk>> wrote:
> >
> >     Hi people
> >
> >     I am trying to generate an array of all possible combinations of 1,
> and
> >     zeros (see example data) for a rather nice Kinetic mote Carlo
> program
> >     which I am writing python. So far, I've been working out for
> >     combinations for 4 or less species by hand as it is quick! but I am
> >     looking to automate the process so I can compute combinations for
> large
> >       numbers of possible species.
> >     I could automate the generation of the array by the use of multiple
> >     loops but that doesn't seem rather pythonic. I was wondering if
> anyone
> >     had any sensible suggestions or pointers for efficient mechanisms
> for
> >     the array.
> >
> >     Many Thanks
> >     Andy
> >
> >     Example Data
> >     3 species
> >     array([[1, 1, 1],
> >            [1, 1, 0],
> >            [1, 0, 1],
> >            [0, 1, 1],
> >            [1, 0, 0],
> >            [0, 1, 0],
> >            [0, 0, 1],
> >            [0, 0, 0]])
> >     4 species
> >     array([[1, 1, 1, 1],
> >            [0, 1, 1, 1],
> >            [1, 0, 1, 1],
> >            [1, 1, 0, 1],
> >            [1, 1, 1, 0],
> >            [1, 1, 0, 0],
> >            [1, 0, 1, 0],
> >            [1, 0, 0, 1],
> >            [0, 1, 1, 0],
> >            [0, 1, 0, 1],
> >            [0, 0, 1, 1],
> >            [1, 0, 0, 0],
> >            [0, 1, 0, 0],
> >            [0, 0, 1, 0],
> >            [0, 0, 0, 1],
> >            [0, 0, 0, 0]])
> >
> >     _______________________________________________
> >     Tutor maillist  -   Tutor at python.org <mailto:Tutor at python.org >
> >     http://mail.python.org/mailman/listinfo/tutor
> >
> >
> _______________________________________________
> Tutor maillist  -   Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>



-- 
Hugh Morgenbesser     hugh at alum.mit.edu    617 504 0734
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.python.org/pipermail/tutor/attachments/20070615/26db01b2/attachment.htm