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

[组合] 相继自然数不相邻地填入方格

本帖最后由 青青子衿 于 2019-5-7 12:27 编辑

1~9九个数字填入3×3的方格中,要求:
1与2不相邻且2与3不相邻且3与4不相邻且4与5不相邻且5与6不相邻且6与7不相邻且7与8不相邻且8与9不相邻;
问:有多少种摆放方案?
一个例子:
\begin{array}{|r|r|r|r|}   
\hline 5 & 2 & 7\\  
\hline 1 & 6 & 3\\   
\hline 9 & 4 & 8\\
\hline \end{array}
如下MMA代码是不考虑旋转翻转等价的方案数:
.
  1. Permutations@Range@9 // Partition[#, 3] & /@ # & //
  2.   Select[#,
  3.     Intersection[{-1, 1},
  4.        Flatten@{{-1, 1}.# & /@
  5.           Partition[#, 2,
  6.            1], {-1, 1}.# & /@
  7.             Partition[#, 2, 1] & /@ #}] == {} &] & // Length
复制代码
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

上面代码运行速度太慢了,没等到结果,换一个速度快一点的,几秒钟就出来结果
  1. c = Select[ArrayReshape[#, {3, 3}] & /@ Permutations@Range[9],
  2.    FreeQ[Differences[#, {1, 0}] // Flatten, 1 | -1] &&
  3.      FreeQ[Differences[#, {0, 1}] // Flatten, 1 | -1] &];
  4. % // Length
复制代码
符合条件(不考虑旋转翻转等价)的结果共有12072种,在其中随便找个验证一下,比如第101个结果c[[101]]
返回
(1        3        8
4        7        2
6        9        5)

TOP

消除对称重复后,应该可以手工分类计数,计算量不会太大。
以中心格的数字作为主索引。对于一种分布,将1,2,3,4,5,6,7,8,9代换成9,8,7,6,5,4,3,2,1可得另一种分布,因此中心数只用考虑1,2,3,4,5即可。这可以使计算量减半。

TOP

返回列表 回复 发帖