Hello,
I need to write scripts in which I need to generate all posible unique
combinations of an integer list. Lists are a minimum 12 elements in
size with very large number of possible combination(12!)
I hacked a few lines of code and tried a few things from Python
CookBook ( http://aspn.activestate.com/ASPN/Cookbook/), but they are
hell slow.
Does any body know of an algorithm/library/module for python that can
help me in generation of these combinations faster
"""ONLY REQUIREMENT IS SPEED"""
Example Problem:
Generate all possible permutations for
[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2] (notice an extra 2 )
eliminate some combinations based on some conditions and combine the
rest of combinations. And now generate all possible combinations for
resulting data set.
Hope you get the idea.
Thanks
PS: Tried matlab/scilab. They are slower than python. 8 5522
Mir Nazim wrote:
Example Problem:
Generate all possible permutations for
[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2] (notice an extra 2 )
eliminate some combinations based on some conditions and combine the
rest of combinations. And now generate all possible combinations for
resulting data set.
Hope you get the idea.
Unfortunately, I don't. Why do you have two lists for which to generate
permutations? Why is it important that the second list has an extra 2
(actually, not extra, but it replaces a 1)?
What are "some conditions" by which to eliminate permutations?
How to "combine" the remaining permutations?
What is the "resulting data set", and what is a "possible combination"
of it?
If the task is to produce all distinct permutations of 6 occurrences
of 1 and 6 occurrences of 2, I suggest the program below. It needs
produces much fewer than 12! results (namely, 924).
Regards,
Martin
numbers = [1,2]
remaining = [None, 6, 6]
result = [None]*12
def permutations(index=0):
if index == 12:
yield result
else:
for n in numbers:
if not remaining[n]:
continue
result[index] = n
remaining[n] = 1
for k in permutations(index+1):
yield k
remaining[n] += 1
for p in permutations():
print p
Martin v. Löwis wrote:
Mir Nazim wrote:
Example Problem:
Generate all possible permutations for
[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]
[1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2] (notice an extra 2 )
eliminate some combinations based on some conditions and combine the
rest of combinations. And now generate all possible combinations for
resulting data set.
Hope you get the idea.
Unfortunately, I don't. Why do you have two lists for which to generate
permutations? Why is it important that the second list has an extra 2
(actually, not extra, but it replaces a 1)?
What are "some conditions" by which to eliminate permutations?
How to "combine" the remaining permutations?
What is the "resulting data set", and what is a "possible combination"
of it?
condition are there cannot be more than 3 consecutive 2's or 1's
If the task is to produce all distinct permutations of 6 occurrences
of 1 and 6 occurrences of 2, I suggest the program below. It needs
produces much fewer than 12! results (namely, 924).
Yes that number I had already worked out and it is 792 for second list.
Now I have generated all distinct permutations and after eliminating
the permutations based on above condition I am left with 1060
permutations.
Now I ahave a lits with 1060 lists in it. Now comes the hard part.
How many possible distinct ways are there to arrange 1060 elements
taken 96 at a time
1060! / (1060  96)!
Hope you got the idea, why i need some faster ways to do it.
Now out of these i need to test only those lists whose sum of
elements(18 or 19) follows a particular pattern.
Can Anybody can alternate ways to do it on a Celeron 1.4 Ghz, 256 MB
RAM laptop.
Thnaks
Regards,
Martin
numbers = [1,2]
remaining = [None, 6, 6]
result = [None]*12
def permutations(index=0):
if index == 12:
yield result
else:
for n in numbers:
if not remaining[n]:
continue
result[index] = n
remaining[n] = 1
for k in permutations(index+1):
yield k
remaining[n] += 1
for p in permutations():
print p
"Mir Nazim" <mi******@gmail.comwrites:
Now I ahave a lits with 1060 lists in it. Now comes the hard part.
How many possible distinct ways are there to arrange 1060 elements
taken 96 at a time
1060! / (1060  96)!
More than you want to think about :
import math
def logf(n):
"""return base10 logarithm of (n factorial)"""
f = 0.0
for x in xrange(1,n+1):
f += math.log(x, 10)
return f
print logf(1060)  logf(1060  96)
Of course there are other ways you can calculate it, e.g. http://en.wikipedia.org/wiki/Stirlings_approximation
Paul Rubin wrote:
1060! / (1060  96)!
More than you want to think about:
import math
def logf(n):
"""return base10 logarithm of (n factorial)"""
f = 0.0
for x in xrange(1,n+1):
f += math.log(x, 10)
return f
print logf(1060)  logf(1060  96)
Of course there are other ways you can calculate it, e.g.
My problem is not to calculate this number, but generate this much
number of permutations in a fastest possible ways.
by the way, logf(1060)  logf(1060  96) = 288.502297251. Do you mean
there are only 289 possible permutation if 1060 elements taken 96 at a
time. Wow it is cool.
Please correct me if I got something wrong
Mir Nazim wrote:
Paul Rubin wrote:
1060! / (1060  96)!
More than you want to think about:
import math
def logf(n):
"""return base10 logarithm of (n factorial)"""
f = 0.0
for x in xrange(1,n+1):
f += math.log(x, 10)
return f
print logf(1060)  logf(1060  96)
Of course there are other ways you can calculate it, e.g.
My problem is not to calculate this number, but generate this much
number of permutations in a fastest possible ways.
by the way, logf(1060)  logf(1060  96) = 288.502297251. Do you mean
there are only 289 possible permutation if 1060 elements taken 96 at a
time. Wow it is cool.
Please correct me if I got something wrong
Not 289, but 10**288.502297251.
That would make generating them all slightly intractable.
Mir Nazim wrote:
condition are there cannot be more than 3 consecutive 2's or 1's
>If the task is to produce all distinct permutations of 6 occurrences of 1 and 6 occurrences of 2, I suggest the program below. It needs produces much fewer than 12! results (namely, 924).
Yes that number I had already worked out and it is 792 for second list.
Now I have generated all distinct permutations and after eliminating
the permutations based on above condition I am left with 1060
permutations.
Again, I don't understand. You have 924 things, eliminate some of them,
and end up with 1060 things? Eliminating elements should decrease
the number, not increase it.
Now I ahave a lits with 1060 lists in it. Now comes the hard part.
How many possible distinct ways are there to arrange 1060 elements
taken 96 at a time
1060! / (1060  96)!
Well, this gives you
31790492142702134948560360823952462727676037031170 29227219760559555570970143122666905356954926552940 84137633231083274081734289102812077377976794152197 86785278711670708872146468499818467251466209986536 33794832176123350796907123110479415043912870243292 225353946234880000000000000000000000000
lists. Assuming you have a 4GHz machine, and assuming you can
process one element per processor cycle (which you can't in
any programming language), you would still need
25201747322664680800165176959627459671229735089398 06274749302828161126149593419161359523207545783343 51326764040369160706600622386171421056868970503708 35541348547430483314423570284610022871849798632147 65501991514557450847370563094938653478495108957455 1507435520000000000000
years to process them all. Even if you had 10000000000
computers (i.e. one per human being on the planet), you
still need ... you get the idea.
Now out of these i need to test only those lists whose sum of
elements(18 or 19) follows a particular pattern.
To succeed, you must take this condition into account.
What is the particular pattern?
Regards,
Martin
Again, I don't understand. You have 924 things, eliminate some of them,
and end up with 1060 things? Eliminating elements should decrease
the number, not increase it.
yes, u are right I had to types of lists:
one one them has 924 permutations and other has 792 making them 1722.
out of which only 1060 are permissible permutations
>
Now I ahave a lits with 1060 lists in it. Now comes the hard part.
How many possible distinct ways are there to arrange 1060 elements
taken 96 at a time
1060! / (1060  96)!
Well, this gives you
31790492142702134948560360823952462727676037031170 29227219760559555570970143122666905356954926552940 84137633231083274081734289102812077377976794152197 86785278711670708872146468499818467251466209986536 33794832176123350796907123110479415043912870243292 225353946234880000000000000000000000000
lists. Assuming you have a 4GHz machine, and assuming you can
process one element per processor cycle (which you can't in
any programming language), you would still need
25201747322664680800165176959627459671229735089398 06274749302828161126149593419161359523207545783343 51326764040369160706600622386171421056868970503708 35541348547430483314423570284610022871849798632147 65501991514557450847370563094938653478495108957455 1507435520000000000000
years to process them all. Even if you had 10000000000
computers (i.e. one per human being on the planet), you
still need ... you get the idea.
I under stand all these calculations.
Now out of these i need to test only those lists whose sum of
elements(18 or 19) follows a particular pattern.
To succeed, you must take this condition into account.
What is the particular pattern?
here is the pattern:
If
A = 18
B = 19
ONLY POSSIBLE Sequence of A, B type rows is as follows
A B A A B A B A A B A A B A A B A B A A B A A B A B A A B A
(REPEATING after this)
I need only thos permutations that follow this pattern. After that I
need to look of a few groupings of elements. like:
(2, 2) = 61 occurs times
(1, 1) = 54 occurs times
(2, 2, 2) = 29 occurs times
(1, 1, 1) = 13 occurs times
and so on. I am looking for the 96 row matrix that satisfies these
groupings.
Again, I don't understand. You have 924 things, eliminate some of them,
and end up with 1060 things? Eliminating elements should decrease
the number, not increase it.
yes, u are right I had to types of lists:
one one them has 924 permutations and other has 792 making them 1722.
out of which only 1060 are permissible permutations
>
Now I ahave a lits with 1060 lists in it. Now comes the hard part.
How many possible distinct ways are there to arrange 1060 elements
taken 96 at a time
1060! / (1060  96)!
Well, this gives you
31790492142702134948560360823952462727676037031170 29227219760559555570970143122666905356954926552940 84137633231083274081734289102812077377976794152197 86785278711670708872146468499818467251466209986536 33794832176123350796907123110479415043912870243292 225353946234880000000000000000000000000
lists. Assuming you have a 4GHz machine, and assuming you can
process one element per processor cycle (which you can't in
any programming language), you would still need
25201747322664680800165176959627459671229735089398 06274749302828161126149593419161359523207545783343 51326764040369160706600622386171421056868970503708 35541348547430483314423570284610022871849798632147 65501991514557450847370563094938653478495108957455 1507435520000000000000
years to process them all. Even if you had 10000000000
computers (i.e. one per human being on the planet), you
still need ... you get the idea.
I under stand all these calculations.
Now out of these i need to test only those lists whose sum of
elements(18 or 19) follows a particular pattern.
To succeed, you must take this condition into account.
What is the particular pattern?
here is the pattern:
If
A = 18
B = 19
ONLY POSSIBLE Sequence of A, B type rows is as follows
A B A A B A B A A B A A B A A B A B A A B A A B A B A A B A
(REPEATING after this)
I need only thos permutations that follow this pattern. After that I
need to look of a few groupings of elements. like:
(2, 2) = 61 occurs times
(1, 1) = 54 occurs times
(2, 2, 2) = 29 occurs times
(1, 1, 1) = 13 occurs times
and so on. I am looking for the 96 row matrix that satisfies these
groupings. This discussion thread is closed Replies have been disabled for this discussion. Similar topics
36 posts
views
Thread by rbt 
last post: by

2 posts
views
Thread by GIMME 
last post: by

7 posts
views
Thread by Venus 
last post: by

2 posts
views
Thread by Girish Sahani 
last post: by

1 post
views
Thread by AAA 
last post: by

9 posts
views
Thread by =?ISO88591?Q?BJ=F6rn_Lindqvist?= 
last post: by

6 posts
views
Thread by py_genetic 
last post: by

4 posts
views
Thread by RSH 
last post: by

14 posts
views
Thread by bjorklund.emil 
last post: by
          