количество всех подмножеств множества

Question

Это то, что я придумал, чтобы вычислить все подмножества длины 0, 1, ..., n из набора длины n с удвоением отдельных элементов.Трудно описать ...

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

Примеры:

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

Какая длина подмножеств (последовательности) зависит от длины последовательности?(Я убил процесс через 50 часов с n = 14)

Спасибо

Майкл

edit: Спасибо всем.Таким образом, это биномиальный коэффициент 2n над n.

Чтобы получить все подмножества вместо мультимножеств (итого общей длиной 2 ^ n), мне нужно было заменить

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

на

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

Answer 1

Количество мультимножеств размера до n из набора размера n равно биномиальному коэффициенту

/ 2n \
|    |
\ n  /

Это следует суммированием числа комбинаций с повторениями для k от 0 до n.

Для n = 14 это дает 40116600 мультимножеств.

Answer 2

Для данного набора A с N количеством элементов количество подмножеств равно 2 ^ N

Answer 3

Количество (нормальных) подмножеств набора составляет 2 ^ N

Число подмножеств длины K с дублированием равно N ^ K. Думайте о своих элементах как о цифрах некоторой системы счисления. Если N равно 10, то ваши элементы просто цифры 0..9.

Если вы хотите, чтобы размер подмножества с дублированием был любым от 1 до N, тогда будет N ^ 1 + N ^ 2 + N ^ 3 + ... + N ^ N множеств.