вычисляет количество возможных упорядочений n объектов по отношениям <и =

Question

Вот проблема:

Дайте алгоритм, который принимает положительное целое число n в качестве входных данных и вычисляет количество возможных упорядочений n объектов при отношениях <и =.Например, если n = 3, 13 возможных порядков выглядят следующим образом: </p>

a = b = c, 
a = b < c, 
a < b = c, 
a < b < c, 
a < c < b, 
a = c < b, 
b < a = c, 
b < a < c, 
b < c < a,
b = c < a, 
c < a = b, 
c < a < b, 
c < b < a. 

Ваш алгоритм должен работать с полиномом по времени от n.

Я не согласен с этой проблемой.Можете ли вы найти какое-либо решение этой проблемы динамического программирования?

Answer 1

Если у вас просто <, тогда можно заказать набор размера N! по-разному. </p>

Если вы добавите обратно в =, то вы можете посчитать разбиения набора в различное количество классов эквивалентности - и умножить на количество способов их упорядочения.

Например, давайте сделаем набор размером 3 (как ваш пример). Мы можем иметь 1, 2 или 3 класса эквивалентности. Есть только 1 способ иметь 1 класс эквивалентности, 3 способа иметь 2 класса эквивалентности и 1 способ иметь 3 класса эквивалентности (см. Позже, как их вычислить). Это дает 1 * 1! + 3 * 2! + 1 * 3! = 13 всего заказов.

Это разбивает исходную задачу на более простую: подсчет способов разбить множество на k частей. Если вы напишите для этого функцию S (N, k), вы можете получить ответ на исходную задачу, вычислив:

sum(k! * S(N, k) for k in 1, 2, ..., N).

Вы можете использовать эти рекуррентные отношения для подсчета разделов (см. http://en.wikipedia.org/wiki/Stirling_number_of_the_second_kind):

S(N, k) = S(N - 1, k - 1) + k * S(N - 1, k)
S(N, 1) = 1
S(N, N) = 1

И вы можете использовать динамическое программирование для вычисления этой функции.

Answer 2

Код

Пусть f (n, k) будет числом возможных упорядочений с ровно k отношениями неравенства (и (n - 1 - k) отношениями качества).

Легко видеть, что f (n, 0) = 1, f (n, n-1) = n!для любого n.

Теперь мы хотим вычислить f (n, k) для любого k.Представьте, что вы удалили одно число (любое), так что теперь есть (n-1) числа.Есть две возможности:

1) Имеются (k-1) неравенства в этих (n-1) числах, и есть (k + 1) (f (n-1, k-1))способы добавления n-го числа для добавления нового неравенства.

2) В этих (n-1) числах имеется k неравенств, а также (k + 1) (f (n-1, k)) способы добавления n-го числа без дополнительного неравенства.

Итак, f (n, k) = (k + 1) (f (n-1, k-1) + f (n-1, k)).

Окончательный ответ F (n) = f (n, 0) + f (n, 1) + ... + f (n, n-1).

Answer 3

у вас может быть рекурсивная функция для этого:

F(1) = 1;
F(2) = 3;


F(n) = F(n-1) * n + F(n-2) * n*(n-1)/2 + F(n-3) * n*(n-1)(n-2)/3!+.... + F(1) * n + 1;

например

F(2) = 1 * 2 +1 = 3;
F(3) = F(2) * 3 + F(1) * 3 + 1 = 9 + 3 + 1 = 13;

Почему?

думаю, вы знаете, F(n-1) теперь вы хотите вставить An в свои последовательности, An может находиться в 0,1,2, ... n-м месте в последовательности, независимо от количества последовательностей: 1011 *

[A0,...An-1] < An this can be as  [A0,...An] < An-1,... 

так что n * f(n-1) последовательности заканчиваются на <

how many sequences end with one `=` sign? f(n-2) * n * (n-1)/ 2 why? ... (think yourself it's easy)

how many sequences end with "K" "=" sing? f(n-k+1) * n * ...*(n-k+1)/ k!

и есть одна полная последовательность =

это можно вычислить полиномиально просто.