количество возможных комбинаций в разбиении - PullRequest
Новая
       14

количество возможных комбинаций в разбиении

2 голосов
/ 28 февраля 2009

Дан набор S размера n, который разбит на классы (s1, .., sk) размеров n1, .., nk. Естественно, что n = n1 + ... + nk.

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

Поскольку я могу выбрать n1 элементов из s1, n2 элементов из s2 и т. Д., Я ищу решение max (n1 * .. * nk) для произвольного n1, .. nk, для которого оно содержит n1 +. . + пк = п.

У меня такое ощущение, что это проблема линейной оптимизации, но прошло слишком много времени с тех пор, как я изучал этот материал как старшекурсник. Я надеюсь, что кто-нибудь помнит, как это вычислить.

Ответы [ 2 ]

3 голосов
/ 28 февраля 2009

Вы ищете количество комбинаций с одним элементом из каждого раздела?

Это просто n1 * n2 * ... * nk.

Edit: Вы, кажется, также задаете отдельный вопрос:

Учитывая N, как мне назначить n1, n2, ..., nk так, чтобы их произведение было максимальным. На самом деле это не проблема линейной оптимизации, поскольку ваши переменные умножаются вместе.

Это может быть решено с помощью некоторого исчисления, то есть путем взятия частичных производных по каждой из переменных с ограничением с использованием множителей Лагранжа.

В результате n1 .. nk будет как можно ближе к тому же размеру. 

if n is a multiple of k, then n_1 = n_2 = ... = n_k = n/k

otherwise, n_1 = n_2 = ... = n_j = Ceiling[n/k]
      and  n_j+1 = ... = n_k = floor[n/k]

По сути, мы стараемся как можно более равномерно распределить элементы по разделам. Если они делятся поровну, отлично. Если нет, мы делим как можно более равномерно, и с тем, что осталось, мы даем дополнительный элемент каждому первому разделу. (Не обязательно должны быть первые разделы, этот выбор довольно произвольный.) Таким образом, разница в количестве элементов, которыми владеют любые два раздела, будет не более одного.

Гори Подробнее :

Это функция продукта, которую мы хотим максимизировать:

P = n1 * n2 * ... nK

Мы определяем новую функцию, используя множители Лагранжа:

Лямбда = P + 1 (N - n1 - n2 ... -nk)

И взять частичные производные в каждой из k n_i переменных:

dLambda / dn_i = P / n_i - l

и в л:

dLambda / dl = N - n1 -n2 ... -nk

установив все частные производные = 0, мы получим систему из k + 1 уравнений, и когда мы решим их, мы получим, что n1 = n2 = ... = nk

Некоторые полезные ссылки:

Множители Лагранжа

Оптимизация

2 голосов
/ 28 февраля 2009 
floor(n/k)^(k - n mod k)*ceil(n/k)^(n mod k)

- MarkusQ

P.S. Для приведенного вами примера S = {1,2,3,4}, n = 4, k = 2 это дает: 

floor(4/2)^(2 - 4 mod 2)*ceil(4/2)^(4 mod 2)
floor(2)^(2 - 0)*ceil(2)^(0)
2^2 * 2^0
4 * 1
4

... как ты хотел.

Для пояснения, эта формула дает число перестановок, порожденных разбиением, с максимально возможным числом перестановок. Конечно, будут и другие, менее оптимальные разбиения.

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

   (length of short sides)^(number of short sides)
times
   (length of long sides)^(number of long sides)

, который является просто объемом гипер-прямоугольника, отвечающего этому ограничению.

Обратите внимание, что при таком рассмотрении он также говорит о том, как построить максимальное разбиение.

...