Re: Generating all possible combination of elements in a list
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 317904921427021349485603608239524627276760370311702922721976055970970143122666905356954926552940841376332310832740817342891028120773779767941521978678527871167070887214646849981846725146620998653633794832176123350796907123110479415043912870243292225353946234880 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 25201747322664680800165176959627459671229735089398062747493028281611261495934191613595232075457833435132676404036916070660062238617142105686897050370835541348547430483314423570284610022871849798632147655019915145574508473705630949386534784951089574551507435520 years to process them all. Even if you had 100 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating all possible combination of elements in a list
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 317904921427021349485603608239524627276760370311702922721976055970970143122666905356954926552940841376332310832740817342891028120773779767941521978678527871167070887214646849981846725146620998653633794832176123350796907123110479415043912870243292225353946234880 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 25201747322664680800165176959627459671229735089398062747493028281611261495934191613595232075457833435132676404036916070660062238617142105686897050370835541348547430483314423570284610022871849798632147655019915145574508473705630949386534784951089574551507435520 years to process them all. Even if you had 100 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating all possible combination of elements in a list
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 317904921427021349485603608239524627276760370311702922721976055970970143122666905356954926552940841376332310832740817342891028120773779767941521978678527871167070887214646849981846725146620998653633794832176123350796907123110479415043912870243292225353946234880 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 25201747322664680800165176959627459671229735089398062747493028281611261495934191613595232075457833435132676404036916070660062238617142105686897050370835541348547430483314423570284610022871849798632147655019915145574508473705630949386534784951089574551507435520 years to process them all. Even if you had 100 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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating all possible combination of elements in a list
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating all possible combination of elements in a list
Mir Nazim [EMAIL PROTECTED] writes: 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 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. http://en.wikipedia.org/wiki/Stirlings_approximation -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating all possible combination of elements in a list
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 -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating all possible combination of elements in a list
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. -- http://mail.python.org/mailman/listinfo/python-list
Generating all possible combination of elements in a list
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. -- http://mail.python.org/mailman/listinfo/python-list
Re: Generating all possible combination of elements in a list
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 -- http://mail.python.org/mailman/listinfo/python-list
