来自减压群的猴子失足撞树枝

kuing

v6mm131(4744*****)  0:04:21

话说这题我初看时连题都没看懂，还以为有啥笑点，刚才突然明白了，题意大概就是要求 A、B、C 顺次排列，而且中间可能还有其他东西，其余的也一样，求排列个数，这样还是可以算嘀。

首先 H、I 的瓜葛少，自由些，先不管它们。
根据五条排列要求，可以排出 A~G 只有两种可能的排列：
G A B C D E F
G A B D C E F
然后再将 H、I 放进去，因 I 要在 C 前，H 在要 D 后，所以：
对于第一种排列，I 有 4 个位，H 有 3 个位；
对于第二种排列，I 有 5 个位，H 有 4 个位；
所以结果就是 4*3+5*4=32？不，还有一点容易漏掉。
注意第二种排列中 H、I 都可以放在 D C 之间，有 D H I C 和 D I H C 两种情况，因此需要再 +1。
所以结果是 33。

不过，这样的方法总感觉很笨，还容易漏，有没有更具一般性的计算方法？
又或者，如果用程序，比如 Mathematica，怎么编程把排列都列出来？

tommywong

或許畫一個有向圖出來就可以完全沒有幫助地裝一次逼呢

$\begin{align*}
I\rightarrow & C\rightarrow E\rightarrow F\\
~ & \uparrow ~~~~~ \uparrow & ~\\
G\rightarrow A\rightarrow & B\rightarrow D\rightarrow H\\
\end{align*}$

业余的业余

用算法的话，这个问题的规模，用回溯法是小case.

这个问题的状态空间是一颗 (不完整的)排列树。

初始状态 0， 第一个分别选 A-H 得到 8个子状态，就像一颗树分的叉。不失一般性，我们考察子树 A.

A 已选，下一步可以选 B-H 7个中之一，于是这一层有7颗子树。 不失一般性，考察 子树 D.

A,D已经排好(前缀), 剩下可选的为{B,C,E,F,G,H} 6个之一，于是这一层有6颗子树。不是一般性，考察子树 B.

ADB里面，D在B前，不满足合法性，从这个分枝已经不可能得到合法的解，所以可以把这颗分枝剪去。这种剪枝叫合法性剪枝。还有一种称为最优性剪枝，对本问题并不适用。

B分枝剪掉，或考察完毕后，回溯到其父节点，即D节点，考察 C. 前缀 ADC, 剩下5个派生出 5颗子树...

注意到每层的子树数比上层少1，如果没有剪枝，其状态空间最底层有 $n!$ 个节点，正是 $n$ 个数的全排列。所以这种状态空间树称为排列树。

阶乘是一种非常可怕的增长方式，所以这个问题虽然好解，如果再增加10来个节点，剪枝又不够有效的话，问题就可能无法在有效时间内求解了。

业余的业余

回复 2# tommywong

是的，这是第一感。然后具体观察，G,A,B,C,D,E,F 仅有两种排法

1. GABCDEF
和
2. GABDCEF

现在只剩两个需要安排的，即 I,H.
1.I =4
1.H=3

2.I=5
2.H=4

综上 总排法 $4\times 3+5\times 4=32$

ps:
噢，漏了一种。觉得用纸笔应该就这样了。

kuing

回复 4# 业余的业余

这1#已经写过，最后果然很容易漏

业余的业余

2. #include <iostream>
4. const int n=9;
6. int p[n]={'A','B','C','D','E','F','G','H','I'};
8. int count;
11. void output()
12. {
13.         for(int i=0; i<n; ++i)
14.                 std::cout<<(char)p[i];
15.         std::cout<<std::endl;
16. }
18. // hard-coded validity check
19. bool is_valid(int t)
20. {
21.         // 可以构建一个map, 这里把逻辑硬编码
22.         switch(p[t])
23.         {
24.         case 'A': // A 前不可有 B,C
25.                 for(int i=0; i<t; ++i)
26.                         if(p[i]=='B' || p[i]=='C')
27.                                 return false;
28.                 break;
29.         case 'B':
30.                 for(int i=0; i<t; ++i)
31.                         if(p[i]=='D' || p[i]=='H' || p[i]=='C')
32.                                 return false;
33.                 break;
34.         case 'C':
35.                 for(int i=0; i<t; ++i)
36.                         if(p[i]=='E')
37.                                 return false;
38.                 break;
39.         case 'D':
40.                 for(int i=0; i<t; ++i)
41.                         if(p[i]=='E' || p[i]=='F' || p[i]=='H')
42.                                 return false;
43.                 break;
44.         case 'E':
45.                 for(int i=0; i<t; ++i)
46.                         if(p[i]=='F')
47.                                 return false;
48.                 break;
49.         //case 'F':
50.         //        break;
51.         case 'G':
52.                 for(int i=0; i<t; ++i)
53.                         if(p[i]=='A' || p[i]=='C')
54.                                 return false;
55.                 break;
56.         //case 'H':
57.         //        break;
58.         case 'I':
59.                 for(int i=0; i<t; ++i)
60.                         if(p[i]=='E' || p[i]=='C')
61.                                 return false;
62.                 break;
63.         }
64.         return true;
65.        
66. }
69. void backtrack(int t)
70. {
71.         if(t==n)
72.         {
73.                 ++count;
74.                 output();
75.         }
76.         else
77.                 for(int i=t; i<n; ++i)
78.                 {
79.                         std::swap(p[t],p[i]);
80.                         if(is_valid(t))
81.                                 backtrack(t+1);
82.                         std::swap(p[t],p[i]);
83.                 }
84. }
86. int main()
87. {
88.         backtrack(0);
89.        
90.         std::cout<<count<<std::endl;
91.         return 0;
92. }

复制代码

33 正确。第33中情形容易忽略，但程序没有盲点。

业余的业余

回复 5# kuing

思路一样，只是我的差之毫厘了

realnumber

一个可以一样高的2346(应该远小于这个值，程序没编好)，都不一样高的33，

var
a,b,c,d,e,f,g,h,i,k:longint;
begin
k:=0;
for a:=3 to 9 do
  for b:=3 to 9 do
    for c:=1 to 9 do
      for d:=1 to 9 do
        for e:=1 to 9 do
          for f:=1 to 9 do
            for g:=4 to 9 do
               for h:=1 to 9 do
                 for i:=3 to 9 do
                 if (a>b)and(b>c)and(d>e)and(e>f)and(g>a)and(a>c)and(b>d)and(d>h)and(i>c)and(c>e) then k:=k+1;
writeln(k);
end.


var
a,b,c,d,e,f,g,h,i,m:longint;
begin
m:=0;
for a:=1 to 9 do
  for b:=1 to 9 do
    for c:=1 to 9 do
      for d:=1 to 9 do
        for e:=1 to 9 do
          for f:=1 to 9 do
            for g:=1 to 9 do
               for h:=1 to 9 do
                 for i:=1 to 9 do
                 begin
                 if (a-d)*(a-e)*(a-f)*(a-h)*(a-i)*(b-e)*(b-f)=0 then continue;
                 if (b-g)*(b-i)*(c-d)*(c-f)*(c-h)*(d-g)*(d-i)*(e-g)=0 then continue;
                 if (e-h)*(e-i)*(f-g)*(f-h)*(f-i)*(g-h)*(g-i)*(h-i)=0 then continue;
                 if (a>b)and(b>c)and(d>e)and(e>f)and(g>a)and(a>c)and(b>d)and(d>h)and(i>c)and(c>e) then m:=m+1;
                 end;
writeln(m);
end.

力工

回复 8# realnumber 都好6！orz

敬畏数学

够狠！

业余的业余

回复 8# realnumber

谢谢