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 <[EMAIL PROTECTED]> 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* <[EMAIL PROTECTED]
> <mailto: [EMAIL PROTECTED]>> 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 - [email protected] <mailto:[email protected] >
> http://mail.python.org/mailman/listinfo/tutor
>
>
_______________________________________________
Tutor maillist - [email protected]
http://mail.python.org/mailman/listinfo/tutor
--
Hugh Morgenbesser [EMAIL PROTECTED] 617 504 0734
_______________________________________________
Tutor maillist - [email protected]
http://mail.python.org/mailman/listinfo/tutor
