Есть 6 мест и 4 человека, для которых места должны быть распределены в соответствии с некоторым критерием оптимальности. Например:Наиболее подходящий алгоритм комбинаторики
Allocation 1:
_ _ _ _ _ _
1 2 3 4
Allocation 2:
_ _ _ _ _ _
1 3 2 4
...
Вопрос 1: Какая проблема комбинаторики?
Вопрос 2. Какое название наиболее подходящего алгоритма для поиска по всем возможным комбинациям?
1.) к-перестановку п без repetion: http://www.statlect.com/comdis1.htm
2.) Это зависит от того, вы ищете. Например, я предлагаю вам генетические алгоритмы, которые могут найти лучшего кандидата на основе специальной эвристики, если вы можете заказать «степень доброты» для возможных решений.
Благодарим вас за комментарий, но я думаю, что k-перестановка правильная. Ваш ответ пишет, что '4! (6 выберите 2) = 4! * (6!/(4! * 2!)) = 6!/2! = n!/(n-k)! ', что является точно решением k-перестановки n. –
Чтобы ответить на вопрос 1, обратите внимание, что для последовательности из 4 человек возможны варианты 4!. Кроме того, незанятые места 6-4=2 должны быть расположены между людьми, для которых есть 4+1=5 слотов (перед каждым человеком и за последним человеком), что дает 5+2-1 choose 2 возможности, где choose обозначает коэффициент биномиального коэффициента, путем интерпретации как проблема stars and bars. В общей сложности, есть
4!(6 choose 2)
возможности или параметризованных
m!(m+1+n-m-1 choose n-m) = m!(n choose n-m)
где m это количество людей и n это количество посадочных мест; используя тождество
n choose k = n!/(k!(n-k)!)
это может быть упрощено до
n!/(n-m)!
, который является действительно n -permutation из m объектов, как определено here.
Что касается Вопроса 2, это действительно зависит от критерия оптимальности и желателен ли точный, приближенный или эвристический алгоритм.
Звучит как максимальный вес, соответствующий мне, предполагая, что веса присвоений не зависят друг от друга. –