Home Original page

Combinations function

Alex Martelli aleaxit at yahoo.com
Mon Feb 26 14:42:11 EST 2001 
"Glen Mettler" <gem at hsv.crc.com> wrote in message
news:97e52o$41c$1 at hobbes2.crc.com...
> Is there a python function that will give me the possible combinations of
a
> set?
> ie - in list a,b,c,d there are 4! or 24 possible combinations.  Is there
an
> existing function to print the possible combinations?

Actually, the term "combinations" is normally used to indicate
samples (of m items out of the n in the set, m <= n), without
replacement, _order not counting_; those are very easy to
generate, but there are 2**n (here, 16) of them, not n!.

You appear to desire _permutations_, aka 'orderings', of n
items, of which there are indeed n!.  Those are easiest to
generate in a recursive way, for example:

def all_permutations(alist):
    if not alist: return [[]]
    result = []
    for i in range(len(alist)):
        for subresult in all_permutations(alist[:i]+alist[i+1:]):
            result.append([alist[i]] + subresult)
    return result

There's a lot of little things that can be done to optimize
this, but this is the basic idea.  Be careful not to run this
on LONG lists -- it will take a LOT of time (and so would
any optimized versions!), because n! grows VERY fast with n.


Alex
More information about the Python-list mailing list