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.

[Martin v. Löwis]

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(in dex=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(in dex+1):
yield k
remaining[n] += 1

for p in permutations():
print p

[Mir Nazim]

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(in dex=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(in dex+1):
yield k
remaining[n] += 1

for p in permutations():
print p

[Paul Rubin]

"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 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]

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

[mensanator]

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.5022972 51.

That would make generating them all slightly intractable.

[Martin v. Löwis]

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

317904921427021 349485603608239 524627276760370 311702922721976 055955557097014 312266690535695 492655294084137 633231083274081 734289102812077 377976794152197 867852787116707 088721464684998 184672514662099 865363379483217 612335079690712 311047941504391 287024329222535 394623488000000 000000000000000 0000

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

252017473226646 808001651769596 274596712297350 893980627474930 282816112614959 341916135952320 754578334351326 764040369160706 600622386171421 056868970503708 355413485474304 833144235702846 100228718497986 321476550199151 455745084737056 309493865347849 510895745515074 355200000000000 00

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

>

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

317904921427021 349485603608239 524627276760370 311702922721976 055955557097014 312266690535695 492655294084137 633231083274081 734289102812077 377976794152197 867852787116707 088721464684998 184672514662099 865363379483217 612335079690712 311047941504391 287024329222535 394623488000000 000000000000000 0000

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

252017473226646 808001651769596 274596712297350 893980627474930 282816112614959 341916135952320 754578334351326 764040369160706 600622386171421 056868970503708 355413485474304 833144235702846 100228718497986 321476550199151 455745084737056 309493865347849 510895745515074 355200000000000 00

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.

[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

>

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

317904921427021 349485603608239 524627276760370 311702922721976 055955557097014 312266690535695 492655294084137 633231083274081 734289102812077 377976794152197 867852787116707 088721464684998 184672514662099 865363379483217 612335079690712 311047941504391 287024329222535 394623488000000 000000000000000 0000

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

252017473226646 808001651769596 274596712297350 893980627474930 282816112614959 341916135952320 754578334351326 764040369160706 600622386171421 056868970503708 355413485474304 833144235702846 100228718497986 321476550199151 455745084737056 309493865347849 510895745515074 355200000000000 00

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.