免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
Board logo

标题: [组合] 三类节目,同类不能相邻的排列数 [打印本页]

作者: 青青子衿    时间: 2019-2-12 14:14     标题: 三类节目,同类不能相邻的排列数

本帖最后由 青青子衿 于 2019-2-12 14:50 编辑

现有A、B、C三类节目,A类节目有\(n_1\)场,B类节目有\(n_2\)场,C类节目有\(n_3\)场;
要求节目表中不能有同类节目相邻,求排列数\(P\left(n_1,n_2,n_3\right)\)。
用MMA求出了个别结果:
\begin{array}{}
P\left(2,1,1\right)=12&P\left(3,1,1\right)=12\\
P\left(2,2,1\right)=48&P\left(3,2,1\right)=120\\
P\left(2,2,2\right)=240&P\left(3,2,2\right)=912\\
&P\left(3,3,1\right)=648\\
&P\left(3,3,2\right)=5328\\
&P\left(3,3,3\right)=37584
\end{array}
  1. Cases[Permutations[{A1, A2, B1, C1}],
  2.   Except[{___, A1, A2, ___} | {___, A2, A1, ___}]] // Length
  3. Cases[Permutations[{A1, A2, B1, B2, C1}],
  4.   Except[{___, A1, A2, ___} | {___, A2, A1, ___} |
  5.     {___, B1, B2, ___} | {___, B2, B1, ___}]] // Length
  6. Cases[Permutations[{A1, A2, B1, B2, C1, C2}],
  7.   Except[{___, A1, A2, ___} | {___, A2, A1, ___} |
  8.     {___, B1, B2, ___} | {___, B2, B1, ___} |
  9.     {___, C1, C2, ___} | {___, C2, C1, ___}]] // Length
  10. Cases[Permutations[{A1, A2, A3, B1, C1}],
  11.   Except[{___, A1, A2, ___} | {___, A2, A1, ___} |
  12.     {___, A1, A3, ___} | {___, A3, A1, ___} |
  13.     {___, A2, A3, ___} | {___, A3, A2, ___}]] // Length
复制代码

作者: 业余的业余    时间: 2019-2-12 20:46

估计 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$ 组合。

以上非解答,。
作者: 业余的业余    时间: 2019-2-12 21:06

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

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

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

有了多项式时间的算法。不知道有没有比较数学的解法。
作者: realnumber    时间: 2019-2-12 22:30

本帖最后由 realnumber 于 2019-2-12 22:56 编辑
这个问题可以变形成如下的或许更简单的问题。

求 $n_1$ 个 $A$, $n_2$ 个 $B$, $n_3$ 个 $C$ 的所有使$A,B ...
业余的业余 发表于 2019-2-12 21:06

记$c(n_1,n_2,n_3)$表示它的不同排法数,$cx(n_1,n_2,n_3)$表示第一个为A的排法数,类似定义$cy(n_1,n_2,n_3)$$cz(n_1,n_2,n_3)$,即$c(n_1,n_2,n_3)=cx(n_1,n_2,n_3)+cy(n_1,n_2,n_3)+cz(n_1,n_2,n_3)$
那么有关系式$cx(n_1,n_2,n_3)=cy(n_1-1,n_2,n_3))+cz(n_1-1,n_2,n_3))$等,因为A后面跟的是B开头的或C开头的.
如此有C(1,1,1)=2+2+2,c(2,1,1)=4+1+1,c(2,2,1)=5+5+2,c(2,2,2)=10+10+10
c(3,1,1)=2+0+0,c(3,2,1)=7+2+1,c(3,2,2)=20+9+9,c(3,3,1)=8+8+2,c(3,3,2)=29+29+16,
c(3,3,3)=58+58+58
c(4,1,1)=0,c(4,2,1)=3+0+0,c(4,2,2)=18+3+3,
c(4,3,2)=(cy(3,3,2)+cz(3,3,2))+(cx(4,2,2)+cz(4,2,2))+(cx(4,2,1)+cy(4,2,1))
=(29+16)+(18+3)+(3+0)
似乎更多的也类似c(w,x,y,z).
作者: kuing    时间: 2019-2-12 23:37

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

求 $n_1$ 个 $A$, $n_2$ 个 $B$, $n_3$ 个 $C$ 的所有使$A,B,C$ 不与自己相邻的排列的个数 ...
业余的业余 发表于 2019-2-12 21:06

是的,先不必考虑同类节目的顺序,最后再乘回 n1!n2!n3! 就是了。
这样连楼主的代码也可以简化不少,比如:
  1. {n1, n2, n3} = {3, 2, 1};
  2. lstall = Join[ConstantArray[a, n1], ConstantArray[b, n2], ConstantArray[c, n3]];
  3. DeleteCases[Permutations[lstall], {___, a, a, ___} | {___, b, b, ___} | {___, c, c, ___}]
  4. % // Length
  5. %*n1!*n2!*n3!
复制代码
不过也没啥用,因为用全排列列出来再删除太bao力了,别说很大的数,我就试下 {n1, n2, n3} = {6, 6, 6} 都卡死。
至于数学的解法,楼上的就很 nice,相应的编程应该也不难吧。
我暂时还没什么更好的想法……
作者: 业余的业余    时间: 2019-2-13 04:40

本帖最后由 业余的业余 于 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倍的运算大概结果就出来了。意思应该到了,不做了。
作者: 业余的业余    时间: 2019-2-13 04:43

回复 5# kuing

多项式展开到特定项的系数的办法能否应用到这类问题?
作者: realnumber    时间: 2019-2-13 09:12

也胡乱提一个,允许同类两个相邻,不允许三个或以上同类相邻呢?
作者: 业余的业余    时间: 2019-2-13 10:12

也胡乱提一个,允许同类两个相邻,不允许三个或以上同类相邻呢?
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函数的第一个参数的类在排列的前缀中最近出现了两次,因此下一个只能从另外两类选取。

边界条件也需要重新考虑,这里不展开了。
作者: Infinity    时间: 2019-4-20 13:57

$n_1$,$n_2$,$n_3$要满足一定约束吧?不然有些情况必然出现同类相邻的问题,比如$n_1=7,n_2=2,n_3=3$时有满足条件的排列吗?




欢迎光临 悠闲数学娱乐论坛(第2版) (http://kuing.orzweb.net/) Powered by Discuz! 7.2