最合适的组合算法

Question

有 6 个座位和 4 个人，必须根据某种最优标准为其分配座位。例如：

Allocation 1:
_ _ _ _ _ _
1 2   3 4 

Allocation 2:
_ _ _ _ _ _
1 3   2   4 

...

问题 1：是哪个组合数学问题？

问题 2：搜索所有可能组合的最合适算法的名称是什么？

Answer 1

要回答问题 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)!

这确实是 m 对象的 n 排列 here。

关于问题 2，这实际上取决于最优性标准以及是否需要精确算法、近似算法或启发式算法。

Answer 2

1.) n 无重复的 k-排列： http://www.statlect.com/comdis1.htm

2.) 这取决于您要搜索的内容。例如，我为您提供遗传算法，如果您可以对可能的解决方案排序 "goodness degree"，它可以根据特殊的启发式算法找到最佳候选者。

最合适的组合算法

Most suitable combinatorics algorithm

java

algorithm

combinations

combinatorics