找回密码
 欢迎注册
查看: 3579|回复: 22

[讨论] 八个人坐成一排,满足条件的坐法有多少种? 编程求解。

[复制链接]
发表于 2023-8-14 08:21:04 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
本帖最后由 TSC999 于 2023-8-14 08:38 编辑

飞机座位图.png

上图表示某客机上的一排座位,其中 A1 和 A8 是靠弦窗的座位,A2 与 A3 及 A6 与 A7 之间都是走道。
有八位旅客 1、2、3、4、5、6、7、8 要坐在这一排座位上,其中旅客 1、2、3、4 对座位有如下要求:
1 不靠弦窗坐(即不坐 A1 和 A8); 1 和 2 必须相邻,且 1 与 2 之间不能是走道(被走道隔开就不算相邻)。
3 与 4 都不靠弦窗坐,且 3 与 4 不能相邻(若被走道隔开也不算相邻,例如 3 坐  A2 位时,4 可以坐在 A3 位)。
5、6、7、8  四位旅客对座位没有要求,可随便分配。
问:共有多少种坐法? 有人算得共有 2208 种坐法,见 http://www.mathchina.com/bbs/for ... &extra=page%3D1
现在的问题是,如何用 mathematica (下简称 MMA)写一个程序来验证 2208 种坐法是否正确。

我想以 MMA 中的全排列指令 Permutations[{1, 2, 3, 4, 5, 6, 7, 8}] 为基础,从中筛选掉不符合要求的那些坐法,剩余的就是答案。但尚未折腾出一个成功的程序。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-8-14 10:01:59 | 显示全部楼层
本帖最后由 TSC999 于 2023-8-14 11:36 编辑

按题目的要求,编程如下。运行结果是 2568,但这个结果有错,因为把每一种符合要求的排列情况打印出来观察,发现有不符合要求的排列出现。
  1. Clear["Global`*"];
  2. aa = Permutations[{1, 2, 3, 4, 5, 6, 7, 8}] ;
  3. n = 0;
  4. For[i = 1, i <= 8!, i++,
  5. a = aa[[i]];
  6. b = a;
  7. If[(1 != b[[1]] &&  1 != b[[8]]) &&  (3 != b[[1]] &&  
  8.      3 != b[[8]]) &&  (4 != b[[1]] &&  4 != b[[8]]),
  9.   If[(1 == b[[2]] &&  2 == b[[1]]) || (1 == b[[7]] &&  
  10.       2 == b[[8]]) || (1 == b[[3]] &&  
  11.       2 == b[[4]]) || (1 == b[[4]] &&  
  12.       2 == b[[3]]) || (1 == b[[4]] &&  
  13.       2 == b[[5]]) || (1 == b[[5]] &&  
  14.       2 == b[[4]]) || (1 == b[[5]] &&  
  15.       2 == b[[6]]) || (1 == b[[6]] &&  2 == b[[5]]),
  16.    If[(3 ==
  17.        b[[2]]) || (4 ==
  18.         b[[2]] || (3 == b[[3]] &&  4 != b[[4]]) || (4 == b[[3]] &&  
  19.          3 != b[[4]])) || (3 ==
  20.         b[[4]] &&  (4 != b[[3]] || (4 != b[[5]]))) || (4 ==
  21.         b[[4]] &&  (3 != b[[3]] || (3 != b[[5]]))) || (3 ==
  22.         b[[5]] &&  (4 != b[[4]] || (4 != b[[6]]))) || (4 ==
  23.         b[[5]] &&  (3 != b[[4]] || (3 != b[[6]]))) || (3 ==
  24.        b[[6]]) || (4 == b[[5]]),
  25.     n = n + 1]]];
  26. ]; Print["n = ", n];
复制代码

点评

上面这程序不对,纠正后的程序代码见 11# 楼。  发表于 2023-8-20 09:37
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-8-14 10:08:16 | 显示全部楼层
我只能建议你穷举法!

点评

原程序中 = 号应该改成 == 号,这样就消除了毛病,能运行了。  发表于 2023-8-14 10:28
2# 楼的程序就是穷举法的思路。但是这个程序有毛病。  发表于 2023-8-14 10:12
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-8-14 14:03:15 | 显示全部楼层
  1. Length@Select[Table[Insert[v,0,{{3},{7}}],{v,Permutations@Range@8}],Length@SequencePosition[#,{1,2}]+Length@SequencePosition[#,{2,1}]==1&&Length@SequencePosition[#,{3,4}]+Length@SequencePosition[#,{4,3}]==0&&Length@Complement[{1,3,4},{#[[1]],#[[10]]}]==3&]
复制代码


2208 是对的

点评

我的 MMA 是 9.0 版本,运行不了上面这程序。  发表于 2023-8-14 14:27
nyy
8!=40320,也没多少,完全穷举  发表于 2023-8-14 14:07
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-8-14 14:04:45 | 显示全部楼层
不知道如何简化
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-8-14 14:43:16 | 显示全部楼层
本帖最后由 nyy 于 2023-8-14 14:45 编辑
  1. Clear["Global`*"];(*清除所有变量*)
  2. fun[list_]:=Module[{aaa,p1,p2,p3,p4},
  3.     aaa=Insert[list,"走道",{{3},{7}}];(*在第3、第7个位置前插入走道*)
  4.     If[Or[aaa[[1]]==1,aaa[[-1]]==1],Return[False]];(*如果最左边最右边为1,那返回错误*)
  5.     {p1,p2,p3,p4}=Flatten[Position[aaa,#]&/@{1,2,3,4}];(*获取1234的位置*)
  6.     If[Abs[p1-p2]!=1,Return[False]];(*如果12位置不相邻,则返回错误*)
  7.     If[Or[aaa[[1]]==3,aaa[[-1]]==3],Return[False]];(*如果最左边最右边为3,那返回错误*)
  8.     If[Or[aaa[[1]]==4,aaa[[-1]]==4],Return[False]];(*如果最左边最右边为4,那返回错误*)
  9.     If[Abs[p3-p4]==1,Return[False]];(*如果34位置相邻,则返回错误*)
  10.     Return[True](*都到这了,肯定返回True*)
  11. ]
  12. aaa=Permutations[{1,2,3,4,5,6,7,8}];(*生成所有可能*)
  13. bbb=Select[aaa,fun[#]&](*只选择符合条件的情况*)
  14. ccc=Length[bbb](*统计个数*)
复制代码


我的代码,简单容易懂

2208个结果

点评

不错,不错!还是你的思路高明!在 13 行后面加个分号,就只显示 2208 了。  发表于 2023-8-14 17:16
nyy
fun子函数,用来判定是否符合要求  发表于 2023-8-14 14:47
nyy
结果太长,被我删除了  发表于 2023-8-14 14:45
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-8-14 20:10:42 | 显示全部楼层
运行结果确实是2208种排法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-8-14 22:02:35 | 显示全部楼层
  1. Length@Select[Table[Insert[v,0,{{3},{7}}],{v,Permutations@Range@8}],SequenceCount[#,{1,2}]+SequenceCount[#,{2,1}]==1&&SequenceCount[#,{3,4}]+SequenceCount[#,{4,3}]==0&&Intersection[{1,3,4},{First@#,Last@#}]=={}&]
复制代码

点评

nyy
看起来牛逼,但是代码可维护性极低,层层嵌套。上面那个点评,是输入法的语音转文字,由于我年纪大了,就喜欢用语音转文字,我现在把正确的搞出来  发表于 2023-8-16 11:07
nyy
看起来牛逼,但是大马可没有微信基地,层层嵌套  发表于 2023-8-14 22:10
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2023-8-15 11:44:25 | 显示全部楼层
2# 楼的程序错误在哪里?需要如何修改才能运行成功?

点评

nyy
扔掉你的垃圾代码吧,看我写的代码多清晰易懂。  发表于 2023-8-15 13:00
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2023-8-15 12:59:23 | 显示全部楼层
TSC999 发表于 2023-8-15 11:44
2# 楼的程序错误在哪里?需要如何修改才能运行成功?

mathematica这种垃圾程序,连个好用的调试器都没有,调试起代码费劲死了。
所以没人对看你的代码感兴趣。唯一的好办法就是自己多写注释、多缩进、不层层嵌套了。

想调试代码,自己就去慢慢print函数debug吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-7-23 06:35 , Processed in 0.058086 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表