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

floor(n/k)^(k - n mod k)*ceil(n/k)^(n mod k)

-- МаркусКью

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)

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

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

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

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

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

Учитывая 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 + l(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

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

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

Оптимизация