Re: [Tutor] Automatic generation of an all possible combinations array
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 i0: 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 i0: 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 - Tutor@python.org mailto:Tutor@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Automatic generation of an all possible combinations array
Luke Paireepinart [EMAIL PROTECTED] wrote
You could also do this by iterating in base-16 instead of base-10...
I was going to suggest the same but using octal which
has the same property but fewer values to map. :-)
hexmap =
{0:,1:0001,2:0010,3:0011,4:0100,5:0101,
6:0110,7:0111,8:1000,9:1001,a:1010,b:1011,c:1100,
d:1101,e:1110,f:}
then for any number n,
you simply do the following:
binary =
for x in hex(n)[2:]:
binary += (hexmap[x])
this is very simple, but I am unsure how efficient it is.
Its very efficient, many of the C standard library routines (tolower
etc)
use a similar technique. The amount of memory used is low and the
speed of a dictionary lookup is much less that multiple divisions etc
You can even avoid the dictionary and just use a list for octal since
n is the number of the index position, but I don't think list indexing
is
any/much faster than a dictionary lookup in Python. (Time for timeit()
here I think...)
HTH,
--
Alan Gauld
Author of the Learn to Program web site
http://www.freenetpages.co.uk/hp/alan.gauld
___
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
Re: [Tutor] Automatic generation of an all possible combinations array
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 i0:
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 i0:
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,
Re: [Tutor] Automatic generation of an all possible combinations array
Another simplest way of doing it is from random import * from sys import * def bin_list(n): bin_val = 0 if n = 0: bin_val = 2**n - 1 list = [] while bin_val = 0: list.append([((bin_val y) 1) for y in range(n-1,-1,-1)]) bin_val -= 1 shuffle(list) return list bin_list(3) gives output as [ [0, 1], [1, 1], [0, 0], [1, 0] ] Output list of patterns is random, we get different patterns for next run. -VishnuMohan 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 i0: 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 - Tutor@python.org mailto:Tutor@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor ___ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
