number of all subsets of a set

This is what I came up with to calculate all subsets of length 0, 1, ... , n of a set of length n with doubling single elements. Difficult to describe...

def subsets(seq, *args):

    seqstart = [[seq[i] for i in args], ]

    if len(args) == 0:
        for i in range(len(seq)):
            seqstart += subsets(seq, i)
    elif len(args) < len(seq):
        for i in range(args[-1], len(seq)):
            seqstart += subsets(seq, *args + (i, ))

    return seqstart

Examples:

>>> subsets(['x', 'y'])
[[], ['x'], ['x', 'x'], ['x', 'y'], ['y'], ['y', 'y']]

>>> subsets(['x', 'y', 'z'])
[[], ['x'], ['x', 'x'], ['x', 'x', 'x'], ['x', 'x', 'y'], ['x', 'x', 'z'], ['x', 'y'], ['x', 'y', 'y'], ['x', 'y', 'z'], ['x', 'z'], ['x', 'z', 'z'], ['y'], ['y', 'y'], ['y', 'y', 'y'], ['y', 'y', 'z'], ['y', 'z'], ['y', 'z', 'z'], ['z'], ['z', 'z'], ['z', 'z', 'z']]

What is the length of subsets(sequence) dependent on the length of the sequence? (I killed the process after 50 hours with n=14)

Thank You

Michael

edit: Thank you all. So it is the Binomial Coefficient of 2n over n.

To obtain all subsets instead of multisets (so a total length of 2^n) I needed to replace

for i i开发者_JAVA百科n range(args[-1], len(seq)):

with

for i in range(args[-1] + 1, len(seq)):

---

The number of multisets of size up to n of a set of size n is equal to the binomial coefficient

/ 2n \
|    |
\ n  /

This follows by summing up the number of combinations with repetition for k from 0 to n.

For n=14, this yields 40116600 multisets.

---

For a given set A with N number of elements, the number of subsets is equal to 2^N

---

A number of (normal) subsets of a set is 2^N

A number of subsets of length K, with duplication, is N^K. Think of your elements like digits of some number system. If N is 10 then your elements are simply digits 0..9.

If you want the size of subset-with-duplication to be any from 1 to N, then there will be N^1+N^2+N^3+...+N^N sets.