Комбинаторное двенадцатизадачие: раскладываем шары по урнам

[wrest]

Если поместил не туда - прошу переместить куда надо (и удалить эту строку из поста).

Иногда возникает необходимость подсчитать количество вариантов раскладки шаров по урнам и аналогичных.

В книжке Кнут "Искусство программирования, Том 4" это называется, вслед за книжкой Стенли "Перечислительная комбинаторика", двенадцатизадачие или "двенадцатиричный путь".

Красивые названия, с простой сутью. Каждая из 12 апостолов задач отвечает на вопрос "сколько существует вариантов сделать то-то и то-то".

Не отвлекаясь на вывод и обоснование формул, приведу только решения как вычислить количество вариантов используя систему компьютерной алгебры PARI/GP. Все задачи даются в терминах раскладок шаров по урнам. Шары и урны будем называть различимыми (и как синонимы -- "пронумерованы", "помечены") или нет (синонимы "непронумерованы", "непомечены") в зависимости от того нанесены ли на них какие-то метки, цвета, номера и т.п., т.е. имеет ли значение какой именно шар кладем в какую именно урну. Порядок следования как шаров в каждой урне, так и порядок следования урн не учитывается.

Шары и урны пронумерованы (помечены).
1. Сколько существует способов разложить n пронумерованных шаров по k пронумерованным урнам?
N=n^k

2. Сколько существует способов разложить n пронумерованных шаров по k пронумерованным урнам так, чтобы в каждой урне было не более одного шара (при условии $k\ge n$)?
N=binomial(k,n)*k!

3. Сколько существует способов разложить n пронумерованных шаров по k пронумерованным урнам так, чтобы в каждой урне было не менее одного шара (при условии $n\ge k$)?
N=k!*stirling(n,k,2)

Шары не пронумерованы (одинаковые), урны пронумерованы.

4. Сколько существует способов разложить n непомеченных шаров в k помеченных урн?
N=binomial(n+k-1,n)

5. Сколько существует способов разложить n непомеченных шаров в k помеченных урн так, чтобы в каждой урне было не более одного шара (ясно, что должно быть $k\ge n$)?
N=binomial(k,n)

6. Сколько существует способов разложить n непомеченных шаров в k помеченных урн так, чтобы в каждой урне было не менее одного шара (при условии $n\ge k$)?
N=binomial(n-1,n-k) или N=binomial(n-1,k-1)

Шары пронумерованы (помечены), урны не пронумерованы (одинаковые).
7. Сколько существует способов разложить n пронумерованных шаров по k непомеченным (одинаковым) урнам?
N=sum(i=1,k,stirling(n,i,2))

8. Сколько существует способов разложить n пронумерованных шаров по k непомеченным (одинаковым) урнам так, чтобы в каждой урне было не более одного шара (при условии $k\ge n$)?
N=1

9. Сколько существует способов разложить n пронумерованных шаров по k непомеченным (одинаковым) урнам так, чтобы в каждой урне было не менее одного шара (при условии $n\ge k$)?
N=stirling(n,k,2)

Шары и урны не пронумерованы (одинаковые).

10. Сколько существует способов разложить n одинаковых шаров в k одинаковых урн?
N=#partitions(n,,[1,k])

11. Сколько существует способов разложить n одинаковых шаров в k одинаковых урн так, чтобы в каждой урне было не более одного шара (при условии $k\ge n$)?
N=1

12. Сколько существует способов разложить n одинаковых шаров в k одинаковых урн так, чтобы в каждой урне было не менее одного шара (при условии $n\ge k$)?
N=#partitions(n,,[k,k])

Обсуждать вроде особо нечего, то есть оставляю это как справку, но если есть ошибки, прошу указать на них.

[maxal]

wrest, использование partitions() в данном случае неэффективно. Все-таки подсчёт и генерация (перечисление) - это задачи существенно разной сложности. Там, где вы используете #partitions(), для больших $n$ гораздо эффективнее будет использовать рекуррентные формулы - см. Wikipedia или MathWorld.

Вычислять числа Белла через сумму чисел Стирлинга тоже не самый оптимальный способ (альтернативы см. по ссылке).

[wrest]

maxal в сообщении #1402525 писал(а):

Вычислять числа Белла через сумму чисел Стирлинга тоже не самый оптимальный способ (альтернативы см. по ссылке).

Спасибо! Вы правы, но
? n=1000;k=300; sum(i=1,k,stirling(n,i,2))
Вычисляется менее чем за 2 секунды на планшете 4-летней свежести с андроидом, получается что-то около $3 \cdot 10^{1927}$
А как, вы думаете, сократится время, если вычислять альтернативно?

[maxal]

wrest, разницу можно почувствовать только для достаточно больших $n$, а что это означает на практике - нужно экспериментировать. К тому же, здесь важно насколько быстро PARI/GP вычисляет сами числа Стирлинга. Например, если они предвычислены и доступны в виде констант, то их суммирование - не такой уж плохой способ.

[wrest]

maxal в сообщении #1402525 писал(а):

Там, где вы используете #partitions(), для больших $n$ гораздо эффективнее будет использовать рекуррентные формулы - см. Wikipedia
или MathWorld
.

У меня рекуррентная формула из Википедии
$P(0,0)=1$
$P(i,0)=0$ для $i>0$
$P(n,k)=P(n,n)$ для $k>n$
$P(n,k)=P(n,k-1)+P(n-k,k)$
Реализованная так:
p(n,k)={
if(n==0& k==0, return (1));
if(k<1,return(0));
if(k>=n,return(numbpart(n)));
return(p(n,k-1)+p(n-k,k))}
Работает намного дольше, чем #partitions()
:(

[wrest]

Например:
?p(40,20)
%1 = 35251
? ##
*** last result computed in 2,201 ms.
? #partitions(60,,[20,20])
%2 = 35251
? ##
*** last result computed in 0 ms.

[wrest]

Оказалось что количество разбиений числа $n$ ровно на $k$ частей равно количеству разбиений числа $n-k$ на не более чем $k$ частей, поэтому перепишем

wrest в сообщении #1401653 писал(а):

Шары и урны не пронумерованы (одинаковые).

10. Сколько существует способов разложить n одинаковых шаров в k одинаковых урн?
N=#partitions(n,,[1,k])

11. Сколько существует способов разложить n одинаковых шаров в k одинаковых урн так, чтобы в каждой урне было не более одного шара (при условии $k\ge n$)?
N=1

12. Сколько существует способов разложить n одинаковых шаров в k одинаковых урн так, чтобы в каждой урне было не менее одного шара (при условии $n\ge k$)?
N=#partitions(n,,[k,k])

Вот так (заодно пронумеруем функции):

Цитата:

Шары и урны не пронумерованы (одинаковые).

10. Сколько существует способов разложить n одинаковых шаров в k одинаковых урн?
N10(n,k)=#partitions(n,k)

11. Сколько существует способов разложить n одинаковых шаров в k одинаковых урн так, чтобы в каждой урне было не более одного шара (при условии $k\ge n$)?
N11(n,k)=if(k>=n,return(1),return(0))

12. Сколько существует способов разложить n одинаковых шаров в k одинаковых урн так, чтобы в каждой урне было не менее одного шара (при условии $n\ge k$)?
N12(n,k)=if(n-k>=k,return(#partitions(n-k,k)),return(numbpart(n-k)))

[_Ivana]

wrest в сообщении #1402591 писал(а):

Работает намного дольше

Да потому что мемоизировать такие вещи надо!

Ссылка на наколеночный неоптимальный вариант мемоизированной реализации https://rextester.com/QKGZ9003

Цитата:

35251
absolute running time: 0.06 sec, cpu time: 0.01 sec

[wrest]

_Ivana в сообщении #1402648 писал(а):

Ссылка на наколеночный неоптимальный вариант мемоизированной реализации

Надо сравнение прямого и мемоизированного вариантов.
n=40 k=20 слишком быстро считается на компе (я ж пример приводил с планшетом...), возьмите хотя бы n=100 k=30 и сравните насколько мемоизация ускоряет, интересно будет посмотреть.

Ну и конечно 14 строк кода... Это не по-нашему, не по pari/gp-шному. У нас one-liner-ы в основном, иногда разбитые на 5-6 строк, для удобства чтения.

[_Ivana]

wrest
Простите, но вы выглядите смешно. Бравировать собственным незнанием такой банальщины, даже как экспоненциально рекурсивный процесс...

Если вам действительно

wrest в сообщении #1402650 писал(а):

интересно

то вы сами

wrest в сообщении #1402650 писал(а):

возьмите

wrest в сообщении #1402650 писал(а):

и сравните

- кот по ссылке изменяемый

Цитата:

164955700
absolute running time: 0.08 sec, cpu time: 0.02 sec

ЗЫ 4 строки на функцию, 8 на мемоизатор (который универсальный для любых функций и во многих языках есть искаропки). Но видимо

wrest в сообщении #1402650 писал(а):

по-нашему, не по pari/gp-шному

писать ересь, подобную вашей

[wrest]

_Ivana
Не, понял, чесговоря, вашей агрессии.
Верю что вы дока в рекурсивных процессах, но в pari/gp, насколько известно мне, нет встроенной мемоизации.
Что такое хаскел я знаю только из статьи в википедии.
Идея первого поста этой темы была в простоте: pari/gp хоть под виндовс, хоть под линукс/андроид, это приложение командной строки, без ide и т.п., которое очень просто устроено и просто работает, это интерпретатор (по сути - калькулятор). Если у вас есть предложения как улучшить код из первого поста (на pari/gp) -- you're welcome. Если вы пришли побравировать собственным знанием, но не хотите его применить и показать как будет лучше (на pari/gp) -- you're not welcome.

[_Ivana]

wrest в сообщении #1402659 писал(а):

you're not welcome

Ох ничеж себе

В теме нет явного ограничения на использование только одной платформы/языка. Да и понятие алгоритма, оно, понимаете, шире. И все ваши примеры прекрасно реализуются на чем угодно. Нет встроенной мемоизации - так в Хаскеле тоже нет, но я добавил, добавьте и вы в вашу систему.

Про виндовс/линукс и без ИДЕ - выше моя ссылка на онлайн-компилятор/интрепретатор, которую можно открыть с любого девайса, с которого можно читать эту тему, например. А вашу систему еще и устанавливать надо.

Вам уже в этой теме написал (как мне кажется по вот этой теме topic14229.html) специалист, что ваши решения, мягко говоря, неоптимальны даже в вашей системе. Ваш ответ также виден всем, читающим тему.

ЗЫ так что если у вас есть способность к конструктивному диалогу хоть с кем-нибудь, то ю а вэлкам. Если нет - не мешайте обсуждать и не захватывайте тему попытками самостоятельного модерирования. Статус ТС не дает вам такого права.

-- 02.07.2019, 13:52 --

Ну и что касается стоимости люстры (С) (кусочек видео из Мимино https://www.youtube.com/watch?v=aht3HJVzq4A):

wrest в сообщении #1402659 писал(а):

на pari/gp

Цитата:

Обсуждение алгоритмов без привязки к языку программирования ведется НЕ ЗДЕСЬ, а в корне раздела Computer Science

Цитата:

Корневой раздел предназначен для обсуждения алгоритмов (без привязки к языку программирования) и других теоретических и практических вопросов информатики, не попадающих под тематику ни одного из подразделов.

topic11190.html

[wrest]

_Ivana в сообщении #1402674 писал(а):

Вам уже в этой теме написал (как мне кажется по вот этой теме topic14229.html ) специалист, что ваши решения, мягко говоря, неоптимальны даже в вашей системе. Ваш ответ также виден всем, читающим тему.

Так я и не спорю с тем, что код #partitions(), вполне вероятно, неоптимальный. И прошу (у вас, в частности) показать мне оптимальный, на pari/gp

Я заглянул в исходные коды pari/gp, в то как реализована там процедура partitions() (если что, это файл \src\modules\part.c в архиве с исходными кодами, которая генерирует разбиения с ограничениями на размер и количество частей, и вижу, что эта процедура работает в два прохода. На первом проходе производится подсчет количества разбиений, который идёт сначала заданием начального разбиения, а затем вызовом функции "следующее разбиение" пока разбиения не закончатся, и соответственно, подсчетом этих вызовов. А на втором проходе, уже зная сколько разбиений получится, создаётся выходной массив нужного размера и опять в цикле генерируются разбиения, но только уже не просто генерируются, а сохраняются. Отсюда я делаю вывод что да, конечно, вызывать генератор только для подсчёта сколько там нагенерилось - может быть неоптимальным. Ну, моя оценка -- примерно в два раза (поскольку делается два прохода как описано выше) плюс время на создание и уничтожение выходного массива с разбиениями. Не в 10 раз, и даже не в 3. А в 2. Допустим, я напишу (перепишу) только функцию подсчета. Исходя из того, что это будет интерпретируемая функция (а не скомпилированная родная), то даже с учетом того что не будет тратиться время на создание большого выходного массива, время потратится на обрамление, которое будет делать интерпретатор. Я не уверен что в итоге можно выиграть по скорости. Несомненное преимущество подсчета разбиений без генерации всего массива -- это требования по памяти, можно будет вычислять с бОльшими числами. Ну не знаю, насколько это может быть практически полезно.

-- 02.07.2019, 14:09 --

_Ivana в сообщении #1402674 писал(а):

Ну и что касается стоимости люстры (С)

Вы можете нажать на кнопку с восклицательным знаком и пожаловаться, что тема не в том разделе.
Ровно об этом же написано у меня первым предложением в стартовом посте.

Моя позиция тут такая. Судя по всему, законченных кодов сюда давать никто не будет, а будут в основном рассуждать о, в частности, экспоненциальных рекурсивных процедурах, отсылая к документации по "вашей системе", "разберитесь там сами" и т.п.

Я бы хотел, чтобы в теме (в первом посте) появились конкретные и работающие коды, которые можно просто скопипастить в свой pari/gp, и которые будут считать обозначенное "двенадцатизадачие". У меня еще были мысли дописать и генераторы, потом поместить тему в карантин и вставить генераторы в первый пост. Но пока мне не очень ясно как лучше оформить возвращаемую структуру.

Так что, я буду рад обсуждению и помощи именно в разрезе реализации полученных добрых советов на pari/gp, а не "вообще" (именно потому, что я оцениваю вероятность что появятся коды ко всем задачам скажем на хаскеле, как близкую к нулю, а на pari/gp поскольку я это уже сделал, вероятность единица) и "добавьте и вы в вашу систему.".

[Geen]

wrest в сообщении #1402680 писал(а):

я буду рад обсуждению и помощи именно в разрезе реализации полученных добрых советов на pari/gp, а не "вообще"

А какое это имеет отношение к "шарам в урнах"?

[wrest]

Geen в сообщении #1402697 писал(а):

А какое это имеет отношение к "шарам в урнах"?

Я не понял вопрос, сорри. Можете переформулировать?