免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖
估计 kuing 有办法。

一些观察。显然 $n_1, n_2, n_3$ 需满足类似三角不等式,任意两个之和 $+1 \ge$ 第三个, 否则没有合法的排列。

先忽略掉同类节目之中不同节目的差异,找出合法的不同类型节目交错排列的个数 $p$, 显然,总个数 为 $p n_1!n_2!n_3!$.

程序搜索的话也是类似的思路,只搜索忽略了同类节目中不同节目差别的不同排列的个数。有可能不是太难。粗粗地想一下它的状态树。

从初始状态 可以派生出 3 个状态,即从不同类中取出一个作为第一个,然后每个状态最多可派生出2个状态,因不可连续同类节目。这样总的忽略组内差别的排法的上限是 $3*2^{n_1+n_2+n_3-1}$, 实际因为合法性剪枝,有效的忽略组内差别的排法会远小于这个数。 这个数有没有可能得到一个解析或递归的表达式,有点存疑。如果不行,状态空间增长蛮快,程序也不能处理太大的 $n_1, n_2, n_3$ 组合。

以上非解答,。

TOP

本帖最后由 业余的业余 于 2019-2-12 21:45 编辑

这个问题可以变形成如下的或许更简单的问题。

求 $n_1$ 个 $A$, $n_2$ 个 $B$, $n_3$ 个 $C$ 的所有使$A,B,C$ 不与自己相邻的排列的个数。

有了多项式时间的算法。不知道有没有比较数学的解法。

TOP

本帖最后由 业余的业余 于 2019-2-13 05:07 编辑

回复 4# realnumber



是的,这是我说的多项式时间算法。也是动态规划。

注意到 当 $a,b,c (1\le a\le b<c)$, 满足$a+b+1=c$ 时,忽略组内差异的排法为 $\cfrac {(a+b)!}{a!b!}$.

当 $a+b \ge c$ 时,排法可以递归的表述如下



$P(a,b,c)=Q(a-1,b,c)+Q(b-1,a,c)+Q(c-1,a,b)$
$Q(a,b,c)=Q(b-1,a,c)+Q(c-1,a,b)$


符号说明: $P(x,y,z)$ 表示 $x$ 个 $A$, $y$ 个 $B$, $z$ 个 $C$ 时,忽略组内差别排法数。

$Q(x,y,z)$ 表示  $x$ 个 $A$, $y$ 个 $B$, $z$ 个 $C$ , 且第一个不可从 $x$ 所在类选择时的忽略组内差别排法数。注意对$Q$函数,第一个位置是特殊的。

这个几乎已经是动态规划的完整算法了 , 是个多项式时间算法。处理 $n_i\le 1000$ 情形 对现在的一般台式电脑,应该不是太大的问题。

笔算个小规模的问题作为示例: $(2,3,5)$, 所求为 $P(2,3,5)=Q(1,3,5)+Q(2,2,5)+Q(4,2,3)$

$Q(1,3,5)=4!/3!=4 $  满足 1+3=5-1
$Q(2,2,5)=4!/2!/2!=6 $ 满足 2+2=5-1
$Q(4,2,3)=Q(1,3,4)+Q(2,2,4)$
$Q(1,3,4)=Q(2,1,4)+Q(3,1,3)$
$Q(2,1,4)=3!/2!=3$  满足边界条件
$Q(3,1,3)=Q(0,3,3)+Q(2,1,3)$
$Q(0,3,3)=Q(2,0,3)+Q(2,0,3)=2\times 2!/2!=2$
$Q(2,1,3)=Q(0,2,3)+Q(2,1,2)=1+Q(2,1,2)$
$Q(2,1,2)=Q(0,2,2)+Q(1,1,2)$
$Q(0,2,2)=2\times Q(1,0,2)=2$
$Q(1,1,2)=Q(0,1,2)+Q(1,1,1)=1+Q(1,1,1)$

$\vdots$

用纸笔还是太复杂了,这个数据表要储存在三维数组里面,纸笔马马虎虎可以模拟,往下再1-2倍的运算大概结果就出来了。意思应该到了,不做了。

TOP

回复 5# kuing

多项式展开到特定项的系数的办法能否应用到这类问题?

TOP

也胡乱提一个,允许同类两个相邻,不允许三个或以上同类相邻呢?
realnumber 发表于 2019-2-13 09:12


没有本质差别。数字会更大,簿记工作量也更大。

P(a,b,c)=Q(a-1,b,c)+Q(b-1,a,b)+Q(c-1,a,b)
Q(a,b,c)=R(a-1,b,c)+Q(b-1,a,c)+Q(c-1,a,b)
R(a,b,c)=Q(b-1,a,c)+Q(c-1,a,b)

P函数只需要一次,也可省略。Q函数的第一个参数的类在排列的前缀中最近出现了1次,因此在换类之前,只能再取一次。R函数的第一个参数的类在排列的前缀中最近出现了两次,因此下一个只能从另外两类选取。

边界条件也需要重新考虑,这里不展开了。
1

评分人数

TOP

返回列表 回复 发帖