435,551 Members | 2,622 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,551 IT Pros & Developers. It's quick & easy.

Generating all possible combination of elements in a list

 P: n/a 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. Jul 23 '06 #1
8 Replies

 P: n/a 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 Jul 23 '06 #2

 P: n/a 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 Jul 24 '06 #3

 P: n/a "Mir Nazim"

 P: n/a Paul Rubin wrote: 1060! / (1060 - 96)! More than you want to think about: import math def logf(n): """return base-10 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 Jul 24 '06 #5

 P: n/a Mir Nazim wrote: Paul Rubin wrote: 1060! / (1060 - 96)! More than you want to think about: import math def logf(n): """return base-10 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. Jul 24 '06 #6

 P: n/a 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 occurrencesof 1 and 6 occurrences of 2, I suggest the program below. It needsproduces 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 Jul 25 '06 #7

 P: n/a 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. Jul 25 '06 #8

 P: n/a 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. Jul 25 '06 #9

This discussion thread is closed

Replies have been disabled for this discussion. 