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

[Andy Cheesman]

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