Generating all possible combination of elements in a list

[Mir Nazim]

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.

 

[=?ISO-8859-1?Q?=22Martin_v=2E_L=F6wis=22?=]

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

 

[Mir Nazim]

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

 

[Paul Rubin]

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

 

[Mir Nazim]

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

 

[mensanator]

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.

 

[=?ISO-8859-1?Q?=22Martin_v=2E_L=F6wis=22?=]

condition are there cannot be more than 3 consecutive 2's or 1's


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

3179049214270213494856036082395246272767603703117029227219760559555570970143122666905356954926552940841376332310832740817342891028120773779767941521978678527871167070887214646849981846725146620998653633794832176123350796907123110479415043912870243292225353946234880000000000000000000000000

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

25201747322664680800165176959627459671229735089398062747493028281611261495934191613595232075457833435132676404036916070660062238617142105686897050370835541348547430483314423570284610022871849798632147655019915145574508473705630949386534784951089574551507435520000000000000

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

 

[Mir Nazim]

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

Well, this gives you

3179049214270213494856036082395246272767603703117029227219760559555570970143122666905356954926552940841376332310832740817342891028120773779767941521978678527871167070887214646849981846725146620998653633794832176123350796907123110479415043912870243292225353946234880000000000000000000000000

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

25201747322664680800165176959627459671229735089398062747493028281611261495934191613595232075457833435132676404036916070660062238617142105686897050370835541348547430483314423570284610022871849798632147655019915145574508473705630949386534784951089574551507435520000000000000

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.

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.

 

[Mir Nazim]

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

Well, this gives you

3179049214270213494856036082395246272767603703117029227219760559555570970143122666905356954926552940841376332310832740817342891028120773779767941521978678527871167070887214646849981846725146620998653633794832176123350796907123110479415043912870243292225353946234880000000000000000000000000

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

25201747322664680800165176959627459671229735089398062747493028281611261495934191613595232075457833435132676404036916070660062238617142105686897050370835541348547430483314423570284610022871849798632147655019915145574508473705630949386534784951089574551507435520000000000000

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.

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.