一幅图像中有多少k个相邻像素的组合?

一旦你得到一个大小为k的像素点的不同形状的数目( here's a reference

• 你能用多少方法在你的图像上放置这个斑点?
• 其中有多少是相同的,这样你就不会重复计算(因为对称性)?

(注:维基百科文章中的引用会处理重复项及其对k的定义。)

如果我理解你的问题,你是在计算长度为k的路径,如下所示:

Start          (end)-> any pixel after visiting k neighbours
*     - - - - -*
|     |
|     |
- - - -

我认为您希望路径是自回避的,这意味着一个像素不应该在行走中被遍历两次(意味着没有循环)。这种情况导致了一个称为SAWs(自回避行走)的经典问题。

here ,从第54页(或第16页)开始,由于页码在文档中重复,因此计数很混乱。但整篇论文很有趣,也很容易阅读。它设法在几张幻灯片中解释了数学背景、历史轶事和马尔可夫链的科学重要性。

如果你打算迭代所有可能的 polyominos ,恐怕您要等很长时间。从维基百科关于polyminos的网站上看,它至少是O(4.0626^n),可能更接近O(8^n)。到n=14时,计数将超过50亿,并且太大,无法放入整数中。到n=30时,计数将超过17/5百万,您将无法将其放入长整数中。如果世界各国政府把他们的资源集中起来,在一个32×32的图标中遍历所有的多星系,他们就无法在太阳变成超新星之前做到这一点。