Количество способов разбить n элементов на множества по 1, 5, 10 элементов?

Question

[MonsterAndrew]

Как можно подсчитать количество способов разбить n элементов на множества по 1, 5, 10 элементов?

Answer 1

[Руслан .]

Есть общая формула для определения количества сочетаний:
C(n,k)=n!/(k!*(n-k)!)

Comments

[longclaps]

Смишно.

[Руслан .]

Аргументируйте.

[longclaps]

Руслан, ну запихните, штоле, в C(n,k) этот набор арументов: n, 1, 5, 10

[Руслан .]

Так запросто, только нужно понимать, что не нужно считать факториалы по отдельности.
Например:
C(100,3)=100!/(97!*3!)=100*99*98/3*2*1= 98*50*33=161700
Вполне просто.

[longclaps]

Руслан, что-то туго идёт разговор: и отвечаете вы в пустоту (надо - адресно, тогда собеседнику приходит уведомление), и отвечаете вы невпопад - я не спрашивал, как посчитать биноминальный коэффициент, я спрашивал - как вы с его помощью можете получить ответ к задаче.
Вы точно Senior Developer?

[Руслан .]

longclaps, С(n,k) - это в первую очередь функция из комбинаторики, которая как раз и даёт ответ на поставленную задачу. В данном случае ответ состоит из трёх вызовов:
С(n,1) - это можно не считать, оно всегда равно n
C(n,3)
C(n,5)

Вот ссылка на вики, там подробно описано:
https://ru.m.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87...

Моя версия решения выглядит так:

def c(n, k):
    t = min(n - k, k)
    n_fact = [n-i for i in range(t)]

    for i in range(t):
        for j in range(len(n_fact)):
            if n_fact[j] % (i + 1) == 0:
                n_fact[j] = n_fact[j] // (i + 1)
                break
    result = 1

    for j in range(len(n_fact)):
        result *= n_fact[j]

    return result

print(c(500, 1))
print(c(500, 5))
print(c(500, 10))

Результат:
500
255244687600
1966484710415128789600

[longclaps]

Руслан, любопытная трактовка задачи. То есть вы решили, что раз задано 3 размера множеств, то и ответов должно быть 3? Вы не находите, что это немного странно: к одной задаче давать 3 условия и ожидать 3 варианта ответов? Вам не кажется, что трактовка "подсчитать количество способов разбить n элементов на множества размером 1, 5 или 10 элементов" более естественна?

[Руслан .]

longclaps, Это скорее вопрос к автору вопроса.

Тут каждый вариант разбиения независим от других.
Если требуется сразу для 3 вариантов, то это будет сумма трех ранее найденных сочетания.
Т.е. вот так:
print(c(500, 1) + c(500, 5) + c(500, 10))

Если взять простой пример (чтобы руками посчитать), например для n=10, то д.б.
c(10, 1) = 10
c(10, 5) = 252
c(10, 10) = 1
Общая сумма 263.

[longclaps]

Руслан, возьмём множество букв "abcdef" и размеры 1,2,3 (числа 5 и 10 великоваты для наглядного примера)
Тогда приемлимыми будут разбиения "a b c d e f", "ad be cf", "abf cde", но также "a bf cde", "a c bde f" - такая трактовка, похоже, кажется вам невероятной.
Тем не менее мною задача прочитана так.
Руслан, что же до вашего решения, то оно неверно и в вашей же постановке задачи. Любопытно, сможете ли вы это понять самостоятельно.

[Руслан .]

longclaps, вы пропустили часть вариантов, вот например для размера 2:
ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df, ef
C(6,2) = 720/(2*24) = 15

решение как раз и дает 15.

[longclaps]

Руслан, читаем внимательно:

количество способов разбить n элементов на множества по 1, 5, 10 элементов

Разницу между "разбить на" и "выбрать k из n" видите?

[Руслан .]

longclaps, нет никакой разницы между разбить и выбрать.
Это стандартная комбинаторная задача: найти количество способов разбить множество на подмножества.

Но тут опять же нужен автор вопрос, чтобы расставить точки на и.

[longclaps]

Руслан, у вас своеобразные познания в комбинаторике. Призовём в помощь вики:
объединение произвольного количества.

[Руслан .]

longclaps, Ок, давайте решим задачу в терминах этой вики.
Дано множество {a, b, c, d, e, f}, требуется найти количество разбиений этого множества непересекающимися подмножествами состоящими из 2 элементов.

Выбираем опорный элемент, например {a} и находим все возможные пары с этим элементом: {a, b},{a, c},{a, d},{a, e},{a, f} - всего 5 пар.
Теперь для каждой пары находим количество разбиений из оставшихся 4 элементов.
Например для пары {a, b} имеем такие варианты:
Вариант 1- {c, d}, {e, f}
Вариант 2- {c, e}, {d, f}
Вариант 3- {c, f}, {d, e}

Т.е. всего имеем 5 исходных пар умноженное на 3 разбиения для каждого, равно 15 возможных разбиений.
Что как раз и есть C(6,2) =15

[longclaps]

Руслан, о боже, что я вижу! Как я это пропустил!

Разбие́ние мно́жества — это представление его в виде объединения произвольного количества попарно непересекающихся подмножеств.

Где тут написано, что они должны быть одного размера?

Но это полбеды. Следи за руками, я повторю твои выкладки для размера 3:

Выбираем опорный элемент, например {a} и находим все возможные тройки с этим элементом: abc,abd,abe,abf,acd,ace,acf,ade,adf,aef - всего 10 троек.
Теперь для каждого подмножества находим количество разбиений из оставшихся 3 элементов.
Например для тройки abc имеем такие варианты:
Вариант 1- def - и всё!

Т.е. всего имеем 10 исходных троек умноженное на 1 разбиение для каждого, равно 10 возможных разбиений.
Что ни разу не есть C(6,3) = 20

Жжешь, Senior Developer!

[Руслан .]

longclaps, И снова вы не все варианты учитываете, вот смотрите:
Для опорного элемента {a} как уже выяснили 10 троек,
но теперь берем опорный элемент {b} и считаем тройки
{bcd} {bce} {bcf} {bde} {bdf} {bef} - т.е. еще 6 троек
теперь берем опорный элемент {c}:
{cde} {cdf} {cef} - еще 3 тройки
и наконец опорный элемент{d}
{def} - 1 тройка.
В итоге 10 + 6 + 3 + 1 = 20, что и есть C(6, 3) = 20

[longclaps]

Руслан, это волшебно )))
итак, допустим (тут правда очень смешно, но приходится оговаривать), что порядок следования подмножеств неважен, как и порядок элементов в подмножествах, т.е.

{{abc}, {def}} == {{def}, {abc}}
 {abc} == {acb} == ... == {cba}

тогда по 2 буквы - 15 разбиений

ab cd ef
ab ce df
ab cf de
ac bd ef
ac be df
ac bf de
ad bc ef
ad be cf
ad bf ce
ae bc df
ae bd cf
ae bf cd
af bc de
af bd ce
af be cd

по 3 буквы - 10 разбиений

abc def
abd cef
abe cdf
abf cde
acd bef
ace bdf
acf bde
ade bcf
adf bce
aef bcd

Ну так?
ps

• если вам кажется, что порядок следования подмножеств и элементов в них важен - для обоих размеров будет по 6! == 720 разбиений, не буду их приводить.
  
• если вам кажется, что порядок следования подмножеств важен, а элементов в них нет - для разбиения по 2 - 90, по 3 - 20.
  
• если вам кажется, что порядок следования подмножеств не важен, а элементов в них важен - для разбиения по 2 - 120, по 3 - 360.

Я в упор не вижу расклада, при котором всплывала бы именно ваша пара чисел - по 2 - 15, по 3 - 20
Не вынуждайте меня присылать эти чертовы разбиения, попробуйте построить их самостоятельно програмкой, и расскажите о своих результатах, посмотрим на расхождения ))))

[Руслан .]

longclaps, Нет, порядок не важен, два подмножества содержащие одинаковые элементы равны и поэтому их не должно быть. Поэтому ваш вариант разбивки 6 элементов на 2 группы правильный, тут я тупанул.

Тут логика даже проще, без перебора: 6 элементов можно разбить по 3 на 20 разных троек, но чтобы покрыть множество из 6 элементов нужны 2 тройки и поэтому разбивок группами по 3 элемента больше чем 10 при двух группах (3 +3 и 20/2 = 10) быть не может.

И да формула в лоб не работает (C(n, k)), тут очень сильно влияет количество групп на которое нужно побить исходное множество, если их больше двух, то появляются дополнительные варианты по переносу элементов из группы в группу.

Теперь по условию задачи, разбить на группы из 1, 5, 10 элементов можно только множество из числа элементов кратного 10 (иначе не выйдет целого количества групп), т.е. процедура определения количества разбиений должна выдавать результат только для чисел вида 10^n, для остальных чисел разбиение не определено.

И теперь например для варианта, где n = 10, количество разбиений:
группами по 1 элементу = 1
группами по 10 элементов = 1
группами по 5 элементов = 126
(
имеем 2 группы по 5 элементов
Берем два опорных элемента 1 и 10, с ними получаем 2 варианта:
вариант 1:
группа 1 {1,_,_,_,_}
группа 2 {10,_,_,_,_}

Из оставшихся 8 элементов выбираем любые 4, это можно сделать C(8, 4) = 70 вариантов

вариант 2:
группа 1 {1,10,_,_,_}
группа 2 {_,_,_ ,_,_}

Из оставшихся 8 элементов выбираем любые 3, это можно сделать C(8, 3) = 56 вариантов

Итого 70+56 = 126 вариантов
)

общее количество = 128

Но если запустить вашу процедуру то получаем 9, как объяснить этот расчет?

[longclaps]

Руслан, на самом деле я там лажу написал ))) Можно как-то так примерно:

from math import factorial as f

def partition(n, steps):
    def merge(aa, bb):
        cc = {}
        for i, a in aa.items():
            for j, b in bb.items():
                k = i + j
                if k <= n:
                    cc[k] = cc.get(k, 0) + a // b
        return cc

    res = {0: f(n)}
    for step in steps:
        res = merge(res, {i * step: f(step) ** i * f(i) for i in range(n // step + 1)})
    return res.get(n, 0)

На простых примерах, где можно посчитать на пальцах, вроде работает:

print(partition(6, [2]))     # 15, как и ожидалось
print(partition(6, [3]))     # 10 -//-
print(partition(6, [2, 3]))  # 25 - тут простая сумма, так как 
                             # в разбиении либо только пары, либо только тройки
print(partition(5, [2, 3]))  # 10 - тут как раз биноминальный коэфф, 
                             # так как делим на 2 и 3 буквы
print(partition(7, [2, 3]))  # 105 - тут возможно лишь разбиение 3+2+2
print(partition(10, [1, 5, 10]))  # 380

[Руслан .]

longclaps, ответ достойный короля :)